Small fast universal Turing machines

DOI10.1016/j.tcs.2006.06.002zbMath1100.68027MaRDI 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 complexity; universality; small universal Turing machine

Mathematics Subject Classification ID

Related Items

How Redundant Is Your Universal Computation Device?, Abstract geometrical computation. IV: Small Turing universal signal machines, On the complex behavior of simple tag systems -- an experimental approach, On small, reduced, and fast universal accepting networks of splicing processors, The complexity of small universal Turing machines: A survey, Computation with finite stochastic chemical reaction networks, Tag systems and Collatz-like functions, Computational classification of cellular automata, The Complexity of Small Universal Turing Machines: A Survey

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