Four states are enough!

DOI10.1016/j.tcs.2010.08.018zbMath1207.68217MaRDI 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 automata; intrinsic universality; bulking; particles and collisions

Mathematics Subject Classification ID

68Q80: Cellular automata (computational aspects)

Related Items

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

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