The complexity of small universal Turing machines: A survey
type: Item
instance of: scholarly article
title: The complexity of small universal Turing machines: A survey
zbMATH Open document ID: 1157.68027
author: Damien Woods
author: Turlough Neary
published in: Theoretical Computer Science
publication date: 2009-03-02T00:00:00Z
full work available at URL: CaltechAUTHORS:20200520-110921412
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q80
zbMATH DE Number: 5522107
zbMATH Keywords: small universal Turing machines
zbMATH Keywords: computational complexity
zbMATH Keywords: polynomial time
zbMATH Keywords: simulation
zbMATH Keywords: tag systems
zbMATH Keywords: cellular automata
MaRDI profile type: Publication
OpenAlex ID: W2063572548
cites work: The Solvability of the Halting Problem for 2-State Post Machines
cites work: Q4530860
cites work: Logical Reversibility of Computation
cites work: Universality of Tag Systems with P = 2
cites work: Q5321501
cites work: Study of Limits of Solvability in Tag Systems
cites work: On Formalisms for Turing Machines
cites work: Q4843270
cites work: DNA Computing
cites work: Q4137150
cites work: Small deterministic Turing machines
cites work: Q4737918
cites work: Q3212314
cites work: Surprising Areas in the Quest for Small Universal Devices
cites work: Q4284259
cites work: Non-erasing turing machines: A new frontier between a decidable halting problem and universality
cites work: Q4850436
cites work: Q4376062
cites work: The laterality problem for non-erasing Turing machines on $\lbrace 0,1\rbrace $ is completely solved
cites work: Frontier between decidability and undecidability: A survey
cites work: On quasi-unilateral universal Turing machines
cites work: Q4850464
cites work: ON THE OPTIMAL NUMBER OF INSTRUCTIONS FOR UNIVERSAL TURING MACHINES CONNECTED WITH A FINITE AUTOMATON
cites work: Busy beaver competition and Collatz-like problems
cites work: Small Turing machines and generalized busy beaver competition
cites work: Recursive unsolvability of Post's problem of ''Tag'' und other topics in theory of Turing machines
cites work: Q5586325
cites work: Quasilinear cellular automata
cites work: Predicting nonlinear cellular automata quickly by decomposing them into linear ones
cites work: A Universal Reversible Turing Machine
cites work: Four Small Universal Turing Machines
cites work: Small fast universal Turing machines
cites work: P-completeness of Cellular Automaton Rule 110
cites work: Small Semi-weakly Universal Turing Machines
cites work: Q5552753
cites work: Q4737167
cites work: Q4071218
cites work: Solvability of the halting problem for certain classes of Turing machines
cites work: Q4083406
cites work: On machines, universal by extensions
cites work: Formal Reductions of the General Combinatorial Decision Problem
cites work: Recursive Unsolvability of a problem of Thue
cites work: Towards a Precise Characterization of the Complexity of Universal and Nonuniversal Turing Machines
cites work: Undecidability and nonperiodicity for tilings of the plane
cites work: MINSKY'S SMALL UNIVERSAL TURING MACHINE
cites work: Q3661558
cites work: Q4383577
cites work: Small universal Turing machines
cites work: Membrane Computing
cites work: Q4079594
cites work: Tag systems and lag systems
cites work: 5-Symbol 8-State and 5-Symbol 6-State Universal Turing Machines
cites work: Statistical mechanics of cellular automata
cites work: Q3150942
cites work: The Complexity of Small Universal Turing Machines
DOI: 10.1016/J.TCS.2008.09.051
Recommended article: The Complexity of Small Universal Turing Machines: A Survey
Recommended article: The Complexity of Small Universal Turing Machines
Recommended article: Small universal Turing machines
Recommended article: Small Semi-Weakly Universal Turing Machines

The complexity of small universal Turing machines: A survey (Recommended article)
Recommended article: Small Semi-weakly Universal Turing Machines
Similarity Score: 0.8965945
Recommender Run: Recommender Run 3

The complexity of small universal Turing machines: A survey (Recommended article)
Recommended article: Small Weakly Universal Turing Machines
Similarity Score: 0.8900405
Recommender Run: Recommender Run 3

The complexity of small universal Turing machines: A survey (Recommended article)
Recommended article: Small fast universal Turing machines
Similarity Score: 0.8854848
Recommender Run: Recommender Run 3

The complexity of small universal Turing machines: A survey (Recommended article)
Recommended article: Q4723304
Similarity Score: 0.8793446
Recommender Run: Recommender Run 3

The complexity of small universal Turing machines: A survey (Recommended article)
Recommended article: Relativizing small complexity classes and their theories
Similarity Score: 0.86994267
Recommender Run: Recommender Run 3

The complexity of small universal Turing machines: A survey (Recommended article)
Recommended article: Relativizing small complexity classes and their theories
Similarity Score: 0.86994267
Recommender Run: Recommender Run 3