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