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

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
• Four colors do not suffice
• State will do

zbMATH Keywords

cellular automataintrinsic universalitybulkingparticles and collisions

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80)

Cites Work

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

Cited In (14)

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

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)