Decision problems for tag systems

DOI10.2307/2270257MaRDI QIDQ5663844zbMATH OpenOpenAlexFDO

Authors 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

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

Cites work

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

Cited in

(3)

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

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

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