Small universal Turing machines

DOI10.1016/S0304-3975(96)00077-1zbMath0874.68106OpenAlexW2065105492WikidataQ56112365 ScholiaQ56112365MaRDI QIDQ1349852

Yurii Rogozhin

Publication date: 27 February 1997

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(96)00077-1

Mathematics Subject Classification ID

Related Items (47)

The Complexity of Small Universal Turing Machines: A Survey ⋮ Integer weighted automata on infinite words ⋮ Universality in Molecular and Cellular Computing ⋮ Abstract geometrical computation. VIII: Small machines, accumulations \& rationality ⋮ Small Universal Devices ⋮ Abstract geometrical computation. IV: Small Turing universal signal machines ⋮ On the complex behavior of simple tag systems -- an experimental approach ⋮ Small networks of polarized splicing processors are universal ⋮ An automaton group with undecidable order and Engel problems ⋮ Direct constructions of universal extended H systems. ⋮ Small Universal Reversible Counter Machines ⋮ Integer Weighted Automata on Infinite Words ⋮ Morphogenetic computing: computability and complexity results ⋮ Spiking neural P systems with polarizations and rules on synapses ⋮ Spiking neural P systems with rules on synapses ⋮ The laterality problem for non-erasing Turing machines on $\lbrace 0,1\rbrace $ is completely solved ⋮ Reversible computing and cellular automata -- a survey ⋮ Encodings of Turing machines in linear logic ⋮ Three small universal spiking neural P systems ⋮ A DNA computing inspired computational model ⋮ On the computational power of networks of polarized evolutionary processors ⋮ Tag systems and Collatz-like functions ⋮ Unnamed Item ⋮ A survey of computational complexity results in systems and control ⋮ Boundedness of the Domain of Definition is Undecidable for Polynomial ODEs ⋮ ON SMALL UNIVERSAL SPLICING SYSTEMS ⋮ Small universal accepting hybrid networks of evolutionary processors ⋮ Small Turing machines and generalized busy beaver competition ⋮ Universal Petri net ⋮ Real recursive functions and their hierarchy ⋮ Analog computation beyond the Turing limit ⋮ How Redundant Is Your Universal Computation Device? ⋮ Small fast universal Turing machines ⋮ The complexity of small universal Turing machines: A survey ⋮ SMALL UNIVERSAL TVDH AND TEST TUBE SYSTEMS ⋮ A new conceptual framework for analog computation ⋮ Average-Case Completeness in Tag Systems ⋮ Closed-form analytic maps in one and two dimensions can simulate universal Turing machines ⋮ Surprising Areas in the Quest for Small Universal Devices ⋮ Maurice Margenstern’s Contributions to the Field of Small Universal Turing Machines ⋮ Computational bounds on polynomial differential equations ⋮ DNA computing based on splicing: Universality results ⋮ Frontier between decidability and undecidability: A survey ⋮ The stability of the deterministic Skorokhod problem is undecidable ⋮ A Note on Computation MTs with Time in Instructions or with Tapes of Fixed Length ⋮ Computing by Floating Strings ⋮ Computational universality and efficiency in morphogenetic systems

Cites Work

• Small deterministic Turing machines
• Automata Studies. (AM-34)
• The Definition of Universal Turing Machine
• Towards a Precise Characterization of the Complexity of Universal and Nonuniversal Turing Machines
• MINSKY'S SMALL UNIVERSAL TURING MACHINE
• A New Hierarchy of Elementary Functions
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Small universal Turing machines