Four states are enough!

DOI10.1016/J.TCS.2010.08.018zbMATH Open1207.68217OpenAlexW1966065489MaRDI QIDQ616491FDOQ616491

Authors 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)

Recommendations

• Four and more
• One is enough!
• Two states
• Four variables suffice
• scientific article; zbMATH DE number 2232819
• Four heads are better than three
• scientific article; zbMATH DE number 5003423
• Four colors do not suffice
• State will do

Cites work

• scientific article; zbMATH DE number 1818513 (Why is no real title available?)
• scientific article; zbMATH DE number 4070331 (Why is no real title available?)
• scientific article; zbMATH DE number 3761989 (Why is no real title available?)
• scientific article; zbMATH DE number 1962850 (Why is no real title available?)
• scientific article; zbMATH DE number 2086632 (Why is no real title available?)
• scientific article; zbMATH DE number 3338162 (Why is no real title available?)
• Bulking I: An abstract theory of bulking
• Bulking II: Classifications of cellular automata
• Endomorphisms and automorphisms of the shift dynamical system
• Global fixed point attractors of circular cellular automata and periodic tilings of the plane: Undecidability results
• P-completeness of Cellular Automaton Rule 110
• Simple Computation-Universal Cellular Spaces
• Tesselations with local transformations
• Theory of cellular automata: a survey
• Tutorial on cellular automata
• Universality in elementary cellular automata
• Upper bound on the products of particle interactions in cellular automata

Cited in

(14)

• An automaton group with undecidable order and Engel problems
• The Simulation Powers and Limitations of Hierarchical Self-Assembly Systems
• Simulating reversible Turing machines and cyclic tag systems by one-dimensional reversible cellular automata
• A particular universal cellular automaton
• Exact Discretization of 3-Speed Rational Signal Machines into Cellular Automata
• Non-isometric contextual array grammars with regular control and local selectors
• scientific article; zbMATH DE number 2086632 (Why is no real title available?)
• Abstract geometrical computation. VIII: Small machines, accumulations \& rationality
• On hardest languages for one-dimensional cellular automata
• The Complexity of Small Universal Turing Machines: A Survey
• A survey of cellular automata: types, dynamics, non-uniformity and applications
• On the complexity of two-dimensional signed majority cellular automata
• Communication complexity meets cellular automata: necessary conditions for intrinsic universality
• The two-handed tile assembly model is not intrinsically universal

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q616491)