Decision problems for tag systems
From MaRDI portal
Publication:5663844
DOI10.2307/2270257zbMath0251.02039OpenAlexW1975748083MaRDI QIDQ5663844
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
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