The complexity of small universal Turing machines: A survey

DOI10.1016/J.TCS.2008.09.051zbMATH Open1157.68027OpenAlexW2063572548MaRDI QIDQ1004087FDOQ1004087

Authors: Damien Woods, Turlough Neary 

Publication date: 2 March 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://resolver.caltech.edu/CaltechAUTHORS:20200520-110921412

Recommendations

• The Complexity of Small Universal Turing Machines: A Survey
• The Complexity of Small Universal Turing Machines
• Small universal Turing machines
• Small Semi-Weakly Universal Turing Machines
• Small Semi-weakly Universal Turing Machines
• Small Weakly Universal Turing Machines
• Small fast universal Turing machines
• scientific article; zbMATH DE number 3997169

zbMATH Keywords

computational complexitysimulationcellular automatapolynomial timetag systemssmall universal Turing machines

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80)

Cites Work

• Title not available (Why is that?)
• Universality in elementary cellular automata
• Formal Reductions of the General Combinatorial Decision Problem
• Logical Reversibility of Computation
• Statistical mechanics of cellular automata
• Title not available (Why is that?)
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Recursive unsolvability of a problem of Thue
• A Universal Reversible Turing Machine
• Busy beaver competition and Collatz-like problems
• Small universal Turing machines
• Small deterministic Turing machines
• Undecidability and nonperiodicity for tilings of the plane
• Frontier between decidability and undecidability: A survey
• Title not available (Why is that?)
• P-completeness of Cellular Automaton Rule 110
• 5-Symbol 8-State and 5-Symbol 6-State Universal Turing Machines
• Small fast universal Turing machines
• Membrane Computing
• Title not available (Why is that?)
• Tag systems and lag systems
• Study of Limits of Solvability in Tag Systems
• Small Semi-weakly Universal Turing Machines
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Surprising areas in the quest for small universal devices
• Non-erasing turing machines: A new frontier between a decidable halting problem and universality
• The Complexity of Small Universal Turing Machines
• Universality of Tag Systems with P = 2
• Four Small Universal Turing Machines
• Small Turing machines and generalized busy beaver competition
• Solvability of the halting problem for certain classes of Turing machines
• MINSKY'S SMALL UNIVERSAL TURING MACHINE
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Predicting nonlinear cellular automata quickly by decomposing them into linear ones
• On Formalisms for Turing Machines
• Towards a Precise Characterization of the Complexity of Universal and Nonuniversal Turing Machines
• Title not available (Why is that?)
• ON THE OPTIMAL NUMBER OF INSTRUCTIONS FOR UNIVERSAL TURING MACHINES CONNECTED WITH A FINITE AUTOMATON
• Title not available (Why is that?)
• Title not available (Why is that?)
• On quasi-unilateral universal Turing machines
• Quasilinear cellular automata
• On machines, universal by extensions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The laterality problem for non-erasing Turing machines on $\lbrace 0,1\rbrace $ is completely solved
• DNA Computing
• The Solvability of the Halting Problem for 2-State Post Machines
• Title not available (Why is that?)

Cited In (22)

• Polarization: a new communication protocol in networks of bio-inspired processors
• Title not available (Why is that?)
• Maurice Margenstern's contributions to the field of small universal Turing machines
• A concrete view of Rule 110 computation
• P-completeness of Cellular Automaton Rule 110
• Universality in elementary cellular automata
• Tag systems and the complexity of simple programs
• Verifiable capacity-bound functions: a new primitive from Kolmogorov complexity. (Revisiting space-based security in the adaptive setting)
• The Complexity of Small Universal Turing Machines
• Small networks of polarized splicing processors are universal
• Small universal reversible counter machines
• Abstract geometrical computation. IV: Small Turing universal signal machines
• Yurii Rogozhin's contributions to the field of small universal Turing machines
• Nontrivial turmites are Turing-universal
• The Complexity of Small Universal Turing Machines: A Survey
• Small Turing universal signal machines
• Small Weakly Universal Turing Machines
• Surprising areas in the quest for small universal devices
• Analysis and design of molecular machines
• Rule primality, minimal generating sets and Turing-universality in the causal decomposition of elementary cellular automata
• Machines, Computations, and Universality
• Looking for small efficient P systems

This page was built for publication: The complexity of small universal Turing machines: A survey

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