Four states are enough!

DOI10.1016/j.tcs.2010.08.018zbMath1207.68217OpenAlexW1966065489MaRDI QIDQ616491

Nicolas Ollinger, Gaétan Richard

Publication date: 10 January 2011

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

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

zbMATH Keywords

cellular automataintrinsic universalitybulkingparticles and collisions

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80)

Related Items

The Complexity of Small Universal Turing Machines: A Survey ⋮ Exact Discretization of 3-Speed Rational Signal Machines into Cellular Automata ⋮ Abstract geometrical computation. VIII: Small machines, accumulations \& rationality ⋮ On the complexity of two-dimensional signed majority cellular automata ⋮ Non-isometric Contextual Array Grammars with Regular Control and Local Selectors ⋮ The Simulation Powers and Limitations of Hierarchical Self-Assembly Systems ⋮ Communication complexity meets cellular automata: necessary conditions for intrinsic universality ⋮ An automaton group with undecidable order and Engel problems ⋮ A survey of cellular automata: types, dynamics, non-uniformity and applications ⋮ Simulating reversible Turing machines and cyclic tag systems by one-dimensional reversible cellular automata ⋮ On hardest languages for one-dimensional cellular automata ⋮ The two-handed tile assembly model is not intrinsically universal

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bulking I: An abstract theory of bulking
• Bulking II: Classifications of cellular automata
• Global fixed point attractors of circular cellular automata and periodic tilings of the plane: Undecidability results
• Theory of cellular automata: a survey
• Tesselations with local transformations
• Tutorial on Cellular Automata
• P-completeness of Cellular Automaton Rule 110
• Endomorphisms and automorphisms of the shift dynamical system
• Simple Computation-Universal Cellular Spaces
• Upper bound on the products of particle interactions in cellular automata

This page was built for publication: Four states are enough!