Decision problems for tag systems

DOI10.2307/2270257zbMath0251.02039OpenAlexW1975748083MaRDI QIDQ5663844

Stål Aanderaa, Dag Belsnes

Publication date: 1971

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

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

Mathematics Subject Classification ID

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

Related Items (3)

The immortality problem for Lag systems ⋮ Diem-Grade Logischer Entscheidungsprobleme ⋮ Halteprobleme von Fang-Systemen (tag systems)

Cites Work

• Unnamed Item
• Unnamed Item
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Tag systems and lag systems
• Automata Studies. (AM-34)
• Universality of Tag Systems with P = 2
• Machine Configuration and Word Problems of Given Degree of Unsolvability
• On a Problem of J.H.C. Whitehead and a Problem of Alonzo Church.
• Monogenic Post Normal Systems of Arbitrary Degree
• Degrees of Unsolvability in Formal Grammars
• The Immortality Problem for Post Normal Systems
• Quantificational variants on the halting problem for turing machines
• On deterministic normal systems
• Formal Reductions of the General Combinatorial Decision Problem

This page was built for publication: Decision problems for tag systems