Non-erasing turing machines: A new frontier between a decidable halting problem and universality

DOI10.1007/3-540-59175-3_104zbMath1495.68056OpenAlexW2155294253MaRDI QIDQ5096346

Maurice Margenstern

Publication date: 16 August 2022

Published in: LATIN '95: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-59175-3_104

zbMATH Keywords

Turing machineshalting problemcomputabilitytag-systems

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Classical models of computation (Turing machines, etc.) (68Q04)

Related Items (5)

Abstract geometrical computation. IV: Small Turing universal signal machines ⋮ On quasi-unilateral universal Turing machines ⋮ The complexity of small universal Turing machines: A survey ⋮ Maurice Margenstern’s Contributions to the Field of Small Universal Turing Machines ⋮ Frontier between decidability and undecidability: A survey

Cites Work

• Solvability of the halting problem for certain classes of Turing machines
• Tag systems and lag systems
• On Computable Numbers, with an Application to the Entscheidungsproblem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Non-erasing turing machines: A new frontier between a decidable halting problem and universality