Small deterministic Turing machines

DOI10.1016/S0304-3975(96)00078-3zbMath0876.03019MaRDI QIDQ1349854

Manfred Kudlek

Publication date: 27 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

context-free languagehalting problemcontext-sensitive languageregular setsbi-infinite tapesmall deterministic Turing machines

Mathematics Subject Classification ID

Turing machines and related notions (03D10)

Related Items

The Complexity of Small Universal Turing Machines: A Survey, Parsimonious computational completeness, Small universal Turing machines, Abstract geometrical computation. IV: Small Turing universal signal machines, Investigations on the power of matrix insertion-deletion systems with small sizes, Spiking neural P systems with rules on synapses, Small Turing machines and generalized busy beaver competition, How Redundant Is Your Universal Computation Device?, Small fast universal Turing machines, Wang's B machines are efficiently universal, as is Hasenjaeger's small universal electromechanical toy, The complexity of small universal Turing machines: A survey, Surprising Areas in the Quest for Small Universal Devices, Maurice Margenstern’s Contributions to the Field of Small Universal Turing Machines, Frontier between decidability and undecidability: A survey

Cites Work

• Busy beaver competition and Collatz-like problems
• 5-Symbol 8-State and 5-Symbol 6-State Universal Turing Machines
• The Halting Problem of one State Turing Machines with n‐Dimensional Tape
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item