Many-one degrees associated with problems of tag

DOI10.2307/2271723zbMath0272.02062OpenAlexW2049922884MaRDI QIDQ3214909

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

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

Related Items (3)

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

Cites Work

• 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
• Formal Reductions of the General Combinatorial Decision Problem

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