The Complexity of Small Universal Turing Machines

DOI10.1007/978-3-540-73001-9_84MaRDI QIDQ5425384zbMATH OpenOpenAlexFDO

Authors Damien Woods, Turlough Neary

Publication date 13 November 2007

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-73001-9_84

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80)

Recommendations

• The complexity of small universal Turing machines: A survey
• The Complexity of Small Universal Turing Machines: A Survey
• Small Weakly Universal Turing Machines
• Small fast universal Turing machines
• Four Small Universal Turing Machines

Cited in

(27)

• The complexity of small universal Turing machines: A survey
• Closed-form analytic maps in one and two dimensions can simulate universal Turing machines
• Some small self-describing Turing machines
• Wang's B machines are efficiently universal, as is Hasenjaeger's small universal electromechanical toy
• Universal Turing machines with complexity constraint
• Yurii Rogozhin's contributions to the field of small universal Turing machines
• A simple universal Turing machine for the game of life Turing machine
• The Complexity of Small Universal Turing Machines: A Survey
• Looking for small efficient P systems
• Small Weakly Universal Turing Machines
• P-completeness of Cellular Automaton Rule 110
• On the Computational Complexity of Small Descriptions
• scientific article; zbMATH DE number 1985715 (Why is no real title available?)
• scientific article; zbMATH DE number 3997169 (Why is no real title available?)
• Surprising areas in the quest for small universal devices
• Nontrivial turmites are Turing-universal
• Rule primality, minimal generating sets and Turing-universality in the causal decomposition of elementary cellular automata
• On the complexity of small description and related topics
• A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory
• Simplicity via provability for universal prefix-free Turing machines
• A concrete view of Rule 110 computation
• Small Turing universal signal machines
• Universality in elementary cellular automata
• Tag systems and the complexity of simple programs
• Machines, Computations, and Universality
• Four Small Universal Turing Machines
• Simplicity via provability for universal prefix-free Turing machines

This page was built for publication: The Complexity of Small Universal Turing Machines

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