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

(26)

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

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)