Small fast universal Turing machines

DOI10.1016/j.tcs.2006.06.002zbMath1100.68027OpenAlexW2081142955MaRDI QIDQ2508974

Damien Woods, Turlough Neary

Publication date: 20 October 2006

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2006.06.002

zbMATH Keywords

computational complexityuniversalitysmall universal Turing machine

Mathematics Subject Classification ID

Related Items

The Complexity of Small Universal Turing Machines: A Survey ⋮ Abstract geometrical computation. IV: Small Turing universal signal machines ⋮ On the complex behavior of simple tag systems -- an experimental approach ⋮ Fractal dimension versus process complexity ⋮ Tag systems and Collatz-like functions ⋮ How Redundant Is Your Universal Computation Device? ⋮ On small, reduced, and fast universal accepting networks of splicing processors ⋮ The complexity of small universal Turing machines: A survey ⋮ Generic case completeness ⋮ Maurice Margenstern’s Contributions to the Field of Small Universal Turing Machines ⋮ Computation with finite stochastic chemical reaction networks ⋮ Unnamed Item ⋮ Computational classification of cellular automata

Cites Work

• Small universal Turing machines
• Small deterministic Turing machines
• Solvability of the halting problem for certain classes of Turing machines
• Universality of Tag Systems with P = 2
• 5-Symbol 8-State and 5-Symbol 6-State Universal Turing Machines
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item