Small fast universal Turing machines

DOI10.1016/J.TCS.2006.06.002MaRDI QIDQ2508974zbMATH OpenOpenAlexFDO

Authors Turlough Neary, Damien Woods

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 complexitysmall universal Turing machineuniversality

Mathematics Subject Classification ID

Recommendations

• Four Small Universal Turing Machines
• Four Small Universal Turing Machines
• Small Weakly Universal Turing Machines
• Small universal Turing machines
• scientific article; zbMATH DE number 1746682

Cites work

• 5-Symbol 8-State and 5-Symbol 6-State Universal Turing Machines
• scientific article; zbMATH DE number 5595151 (Why is no real title available?)
• scientific article; zbMATH DE number 3664359 (Why is no real title available?)
• scientific article; zbMATH DE number 1142308 (Why is no real title available?)
• scientific article; zbMATH DE number 1746682 (Why is no real title available?)
• scientific article; zbMATH DE number 2087234 (Why is no real title available?)
• scientific article; zbMATH DE number 3305022 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• Small deterministic Turing machines
• Small universal Turing machines
• Solvability of the halting problem for certain classes of Turing machines
• Universality in elementary cellular automata
• Universality of Tag Systems with P = 2

Cited in

(25)

• 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
• Some small self-describing Turing machines
• Small universal Turing machines
• Tag systems and Collatz-like functions
• Wang's B machines are efficiently universal, as is Hasenjaeger's small universal electromechanical toy
• Yurii Rogozhin's contributions to the field of small universal Turing machines
• Computational classification of cellular automata
• The Complexity of Small Universal Turing Machines: A Survey
• MINSKY'S SMALL UNIVERSAL TURING MACHINE
• scientific article; zbMATH DE number 1992427 (Why is no real title available?)
• scientific article; zbMATH DE number 1746682 (Why is no real title available?)
• Maurice Margenstern's contributions to the field of small universal Turing machines
• Fractal dimension versus process complexity
• Presburger arithmetic with algebraic scalar multiplications
• How Redundant Is Your Universal Computation Device?
• The Complexity of Small Universal Turing Machines
• Four Small Universal Turing Machines
• Four Small Universal Turing Machines
• Abstract geometrical computation. IV: Small Turing universal signal machines
• On the complex behavior of simple tag systems -- an experimental approach
• Decidability for Sturmian words
• Uncloneable quantum advice
• Generic case completeness

This page was built for publication: Small fast universal Turing machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2508974)