Abstract
This chapter reviews some fundamental concepts and outcomes of the idea of cellular automata (CA). Topics discussed include classical is a result of the 1960s, relations between various concepts of injectivity and surjectivity, and dynamical system concepts associated with chaos in CA. Most answers are reported without full proofs but may examples are supplied that illustrate the thought of an evidence. The classical results discussed range from the GardenofEden theorem and also the Curtis–Hedlund–Lyndon theorem, along with the balance property of surjective CA. Different variants of sensitivity to initial conditions and mixing qualities are introduced and associated with one another. Also, algorithmic aspects and undecidability answers are pointed out.
Keywords
Cellular Automaton Cellular Automaton Local Rule Moore Neighborhood Algorithmic Question
References

Berlekamp ER, Conway JH, Guy RK (1982) Winning methods for your mathematical plays, vol II, chap 25. Academic, LondonGoogle Scholar

Burks A (1970) Von Neumann's selfreproducing automata. In: Burks A (erectile dysfunction) Essays on cellular automata, College of Illinois Press, Champaign, pp 3–64

Czeizler E, Kari J (2005) A good straight line bound around the neighborhood of inverse cellular automata. In: Caires L, Italiano GF, Monteiro L, Palamidessi C, Yung M (eds) ICALP, Lecture notes in information technology, vol 3580, Springer, Berlin, pp 410–420Google Scholar

Devaney RL (1986) Introducing chaotic dynamical systems. Benjamin/Cummings, Menlo Park, CAzbMATH

Durand B (1998) Global qualities of cellular automata. In: Goles E, Martinez S (eds) Cellular automata and sophisticated systems. Kluwer, Dordrecht

Durand B, Formenti E, Varouchas G (2003) On undecidability of equicontinuity classification for cellular automata. In: Morvan M, Remila E (eds) Discrete models for complex systems, DMCS’03, DMTCS Conference Volume AB, Lyon, France, pp 117–128Google Scholar

Gardner M (1970) The great mixtures of John Conway's new solitaire game “; Existence ”. Sci Am 223(4): 120–123CrossRef

Kari J, Ollinger N (2008) Periodicity and growing old in reversible computing. In: Ochmanski E, Tyszkiewicz J (eds) MFCS, Lecture notes in information technology, vol 5162, Springer, Berlin, pp 419–430Google Scholar

Kari J, Vanier P, Zeume T (2009) Bounds on nonsurjective cellular automata. In: Královic R, Urzyczyn P (eds) MFCS, Lecture notes in information technology, vol 5734, Springer, Berlin, pp 439–450Google Scholar

Lukkarila V (2010) Sensitivity and topological mixing are undecidable for reversible onedimensional cellular automata. J Cell Autom 5:241–272MathSciNetzbMATH

Moore EF (1962) Machine types of selfreproduction. In: Bellman RE (erectile dysfunction) Proceedings of symposia in applied mathematics XIV: “;Mathematical problems within the biological sciences”, AMS, pp 17–33

von Neumann J (1966) Theory of selfreproducing automata. In: Burks AW (erectile dysfunction) College of Illinois Press, Urbana, London

Sablik M, Theyssier G (2008) Topological dynamics of 2D cellular automata. In: CiE ’08: Proceedings from the fourth conference on computability in Europe, Springer, Berlin, Heidelberg, pp 523–532

Wang H (1961) Showing theorems by pattern recognition – ii. Bell Syst Tech J 40:1–42

Wolfram S (erectile dysfunction) (1986) Theory and applying cellular automata.
URL:https://link.springer.com/referenceworkentry/10.1007%2F9783540929109_1
H:Fundamental Concepts of Cellular Automata
Key:Fundamental Concepts of Cellular Automata