The complexity of small universal Turing machines: A survey

DOI10.1016/j.tcs.2008.09.051zbMath1157.68027OpenAlexW2063572548MaRDI QIDQ1004087

Turlough Neary, Damien Woods

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

zbMATH Keywords

computational complexitysimulationcellular automatapolynomial timetag systemssmall universal Turing machines

Mathematics Subject Classification ID

Related Items (7)

The Complexity of Small Universal Turing Machines: A Survey ⋮ Abstract geometrical computation. IV: Small Turing universal signal machines ⋮ Small networks of polarized splicing processors are universal ⋮ Verifiable capacity-bound functions: a new primitive from Kolmogorov complexity. (Revisiting space-based security in the adaptive setting) ⋮ Small Universal Reversible Counter Machines ⋮ Analysis and design of molecular machines ⋮ Polarization: a new communication protocol in networks of bio-inspired processors

Cites Work

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

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