The Complexity of Small Universal Turing Machines: A Survey
From MaRDI portal
Publication:2891384
DOI10.1007/978-3-642-27660-6_32zbMath1302.68117OpenAlexW1646814793MaRDI QIDQ2891384
Publication date: 15 June 2012
Published in: SOFSEM 2012: Theory and Practice of Computer Science (Search for Journal in Brave)
Full work available at URL: https://resolver.caltech.edu/CaltechAUTHORS:20200520-110921412
Related Items
Parsimonious computational completeness ⋮ Universality in Molecular and Cellular Computing ⋮ Small Universal Devices ⋮ On Goles' universal machines: a computational point of view ⋮ Investigations on the power of matrix insertion-deletion systems with small sizes ⋮ Small Universal Reversible Counter Machines ⋮ Linear Bounds on the Size of Conformations in Greedy Deterministic Oritatami ⋮ The instructional information processing account of digital computation ⋮ Wang's B machines are efficiently universal, as is Hasenjaeger's small universal electromechanical toy ⋮ Maurice Margenstern’s Contributions to the Field of Small Universal Turing Machines
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
- Four states are enough!
- 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
- The complexity of small universal Turing machines: A survey
- Complexity of Langton's ant
- 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
- Small Weakly Universal Turing Machines
- A Decision Procedure for Computations of Finite Automata
- 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
- Small Semi-Weakly Universal Turing Machines
- Statistical mechanics of cellular automata
- The Determination of the Value of Rado's Noncomputable Function | sum(k) for Four-State Turing Machines
- 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
- DNA Computing
- Computer Studies of Turing Machine Problems
- 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
- Counter machines and counter languages
- The Halting Problem of one State Turing Machines with n‐Dimensional Tape
- Logical Reversibility of Computation
- On Computable Numbers, with an Application to the Entscheidungsproblem
- Formal Reductions of the General Combinatorial Decision Problem
- Four Small Universal Turing Machines
- Four Small Universal Turing Machines
- On quasi-unilateral universal Turing machines
