Tag systems and lag systems

DOI10.1007/BF01343730zbMath0131.24602MaRDI QIDQ2395198

Hao Wang

Publication date: 1963

Published in: Mathematische Annalen (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/161095

zbMATH Keywords

mathematical logic

Related Items (17)

The undecidability of the Turing machine immortality problem ⋮ The Complexity of Small Universal Turing Machines: A Survey ⋮ The decision problem for formulas in prenex conjunctive normal form with binary disjunctions ⋮ The Solvability of the Derivability Problem for One-Normal Systems ⋮ Non-erasing turing machines: A new frontier between a decidable halting problem and universality ⋮ On the complex behavior of simple tag systems -- an experimental approach ⋮ Decision problems for tag systems ⋮ The immortality problem for Lag systems ⋮ Tag systems and Collatz-like functions ⋮ Undecidability of the problem of recognizing axiomatizations of superintuitionistic propositional calculi ⋮ Beitrag zur Reduktion des Entscheidungsproblems auf Klassen von Hornformeln mit kurzen Alternationen ⋮ On quasi-unilateral universal Turing machines ⋮ Halteprobleme von Fang-Systemen (tag systems) ⋮ The complexity of small universal Turing machines: A survey ⋮ On biconjunctive reduction classes ⋮ Frontier between decidability and undecidability: A survey ⋮ Context free normal systems and ETOL systems

Cites Work

• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Formal Reductions of the General Combinatorial Decision Problem

This page was built for publication: Tag systems and lag systems