On Goles' universal machines: a computational point of view

DOI10.1016/j.tcs.2013.04.024zbMath1297.68075OpenAlexW2007797006MaRDI QIDQ393156

Bruno Martin

Publication date: 16 January 2014

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.04.024

zbMATH Keywords

universalitydiscrete dynamical systemscomputabilityabstract machines

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Cellular automata (computational aspects) (68Q80) Dynamical aspects of cellular automata (37B15) Symbolic dynamics (37B10)

Related Items

Computational universality of fungal sandpile automata, On fungal automata

Cites Work

• Reaction-diffusion automata: Three states implies universality
• Crossing information in two-dimensional sandpiles
• The computational complexity of sandpiles
• A universal cellular automaton in quasi-linear time and its S-m-n form
• Analog computation via neural networks
• Complexity of Langton's ant
• Universality of the chip-firing game
• Frontier between decidability and undecidability: A survey
• The Complexity of Small Universal Turing Machines: A Survey
• The Definition of Universal Turing Machine
• On the computational power of totalistic cellular automata
• On Relating Time and Space to Size and Depth
• Spatial Patterns for Discrete Models of Diffusion in Excitable Media
• Cellular automata universality revisited
• Simple Computation-Universal Cellular Spaces
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item