Many-one degrees associated with problems of tag

DOI10.2307/2271723MaRDI QIDQ3214909zbMATH OpenOpenAlexFDO

Authors Charles E. Hughes

Publication date 1973

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2307/2271723

Mathematics Subject Classification ID

Thue and Post systems, etc. (03D03) Turing machines and related notions (03D10) Other degrees and reducibilities in computability and recursion theory (03D30) Word problems, etc. in computability and recursion theory (03D40)

Cites work

• Formal Reductions of the General Combinatorial Decision Problem
• Machine Configuration and Word Problems of Given Degree of Unsolvability
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• The many-one equivalence of some general combinatorial decision problems

Cited in

(3)

• Single premise Post canonical forms defined over one-letter alphabets
• Diem-Grade Logischer Entscheidungsprobleme
• Combinatorial systems defined over one- and two-letter alphabets

This page was built for publication: Many-one degrees associated with problems of tag

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3214909)