Surprising Areas in the Quest for Small Universal Devices

DOI10.1016/j.entcs.2008.12.075zbMath1336.68071MaRDI QIDQ4982064

Maurice Margenstern

Publication date: 23 March 2015

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

Full work available at URL: https://doi.org/10.1016/j.entcs.2008.12.075

zbMATH Keywords

Turing machines; cellular automata; universality; hyperbolic geometry; super-Turing computations

Mathematics Subject Classification ID

68Q80: Cellular automata (computational aspects)

Related Items

A universal cellular automaton on the heptagrid of the hyperbolic plane with four states, Reversible computing and cellular automata -- a survey, The complexity of small universal Turing machines: A survey, The Complexity of Small Universal Turing Machines: A Survey

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
• Reversibility of 2D cellular automata is undecidable
• Computation and construction universality of reversible cellular automata
• Small universal Turing machines
• Small deterministic Turing machines
• A universal cellular automaton in the hyperbolic plane.
• A computation-universal two-dimensional 8-state triangular reversible cellular automaton
• Solvability of the halting problem for certain classes of Turing machines
• Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures
• ON THE OPTIMAL NUMBER OF INSTRUCTIONS FOR UNIVERSAL TURING MACHINES CONNECTED WITH A FINITE AUTOMATON
• Recursive Unsolvability of a problem of Thue
• Shorter Note: The Converse of Moore's Garden-of-Eden Theorem
• 5-Symbol 8-State and 5-Symbol 6-State Universal Turing Machines
• Endomorphisms and automorphisms of the shift dynamical system
• Four Small Universal Turing Machines