Many-one degrees associated with problems of tag

DOI10.2307/2271723zbMATH Open0272.02062OpenAlexW2049922884MaRDI QIDQ3214909FDOQ3214909

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
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Machine Configuration and Word Problems of Given Degree of Unsolvability
• 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)