Skip to main content
Erschienen in:
Buchtitelbild

2012 | OriginalPaper | Buchkapitel

Basic Concepts of Cellular Automata

verfasst von : Jarkko J. Kari

Erschienen in: Handbook of Natural Computing

Verlag: Springer Berlin Heidelberg

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

This chapter reviews some basic concepts and results of the theory of cellular automata (CA). Topics discussed include classical results from the 1960s, relations between various concepts of injectivity and surjectivity, and dynamical system concepts related to chaos in CA. Most results are reported without full proofs but sometimes examples are provided that illustrate the idea of a proof. The classical results discussed include the Garden-of-Eden theorem and the Curtis–Hedlund–Lyndon theorem, as well as the balance property of surjective CA. Different variants of sensitivity to initial conditions and mixing properties are introduced and related to each other. Also, algorithmic aspects and undecidability results are mentioned.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literatur
Zurück zum Zitat Amoroso S, Patt Y (1972) Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures. J Comput Syst Sci 6:448–464MathSciNetMATHCrossRef Amoroso S, Patt Y (1972) Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures. J Comput Syst Sci 6:448–464MathSciNetMATHCrossRef
Zurück zum Zitat Berger R (1966) The undecidability of the domino problem. Mem Amer Math Soc 66:1–72 Berger R (1966) The undecidability of the domino problem. Mem Amer Math Soc 66:1–72
Zurück zum Zitat Berlekamp ER, Conway JH, Guy RK (1982) Winning ways for your mathematical plays, vol II, chap 25. Academic, London Berlekamp ER, Conway JH, Guy RK (1982) Winning ways for your mathematical plays, vol II, chap 25. Academic, London
Zurück zum Zitat Blanchard F, Tisseur P (2000) Some properties of cellular automata with equicontinuity points. Ann Inst Henri Poincaré, Probab Stat 36(5):569–582MathSciNetMATHCrossRef Blanchard F, Tisseur P (2000) Some properties of cellular automata with equicontinuity points. Ann Inst Henri Poincaré, Probab Stat 36(5):569–582MathSciNetMATHCrossRef
Zurück zum Zitat Burks A (1970) Von Neumann's self-reproducing automata. In: Burks A (ed) Essays on cellular automata, University of Illinois Press, Champaign, pp 3–64 Burks A (1970) Von Neumann's self-reproducing automata. In: Burks A (ed) Essays on cellular automata, University of Illinois Press, Champaign, pp 3–64
Zurück zum Zitat Czeizler E, Kari J (2005) A tight linear bound on the neighborhood of inverse cellular automata. In: Caires L, Italiano GF, Monteiro L, Palamidessi C, Yung M (eds) ICALP, Lecture notes in computer science, vol 3580, Springer, Berlin, pp 410–420 Czeizler E, Kari J (2005) A tight linear bound on the neighborhood of inverse cellular automata. In: Caires L, Italiano GF, Monteiro L, Palamidessi C, Yung M (eds) ICALP, Lecture notes in computer science, vol 3580, Springer, Berlin, pp 410–420
Zurück zum Zitat Devaney RL (1986) An introduction to chaotic dynamical systems. Benjamin/Cummings, Menlo Park, CAMATH Devaney RL (1986) An introduction to chaotic dynamical systems. Benjamin/Cummings, Menlo Park, CAMATH
Zurück zum Zitat Durand B (1998) Global properties of cellular automata. In: Goles E, Martinez S (eds) Cellular automata and complex systems. Kluwer, Dordrecht Durand B (1998) Global properties of cellular automata. In: Goles E, Martinez S (eds) Cellular automata and complex systems. Kluwer, Dordrecht
Zurück zum Zitat 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–128 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–128
Zurück zum Zitat Gardner M (1970) The fantastic combinations of John Conway's new solitaire game “ Life ”. Sci Am 223(4): 120–123CrossRef Gardner M (1970) The fantastic combinations of John Conway's new solitaire game “ Life ”. Sci Am 223(4): 120–123CrossRef
Zurück zum Zitat Kari J, Ollinger N (2008) Periodicity and immortality in reversible computing. In: Ochmanski E, Tyszkiewicz J (eds) MFCS, Lecture notes in computer science, vol 5162, Springer, Berlin, pp 419–430 Kari J, Ollinger N (2008) Periodicity and immortality in reversible computing. In: Ochmanski E, Tyszkiewicz J (eds) MFCS, Lecture notes in computer science, vol 5162, Springer, Berlin, pp 419–430
Zurück zum Zitat Kari J, Vanier P, Zeume T (2009) Bounds on non-surjective cellular automata. In: Královic R, Urzyczyn P (eds) MFCS, Lecture notes in computer Science, vol 5734, Springer, Berlin, pp 439–450 Kari J, Vanier P, Zeume T (2009) Bounds on non-surjective cellular automata. In: Královic R, Urzyczyn P (eds) MFCS, Lecture notes in computer Science, vol 5734, Springer, Berlin, pp 439–450
Zurück zum Zitat Kůrka P (1997) Languages, equicontinuity and attractors in cellular automata. Ergod Theor Dyn Syst 17:417–433MATHCrossRef Kůrka P (1997) Languages, equicontinuity and attractors in cellular automata. Ergod Theor Dyn Syst 17:417–433MATHCrossRef
Zurück zum Zitat Lukkarila V (2010) Sensitivity and topological mixing are undecidable for reversible one-dimensional cellular automata. J Cell Autom 5:241–272MathSciNetMATH Lukkarila V (2010) Sensitivity and topological mixing are undecidable for reversible one-dimensional cellular automata. J Cell Autom 5:241–272MathSciNetMATH
Zurück zum Zitat Moore EF (1962) Machine models of self-reproduction. In: Bellman RE (ed) Proceedings of symposia in applied mathematics XIV: “Mathematical problems in the biological sciences”, AMS, pp 17–33 Moore EF (1962) Machine models of self-reproduction. In: Bellman RE (ed) Proceedings of symposia in applied mathematics XIV: “Mathematical problems in the biological sciences”, AMS, pp 17–33
Zurück zum Zitat Myhill J (1963) The converse of Moore's Garden-of-Eden theorem. Proc Am Math Soc 14:685–686MathSciNetMATH Myhill J (1963) The converse of Moore's Garden-of-Eden theorem. Proc Am Math Soc 14:685–686MathSciNetMATH
Zurück zum Zitat von Neumann J (1966) Theory of self-reproducing automata. In: Burks AW (ed) University of Illinois Press, Urbana, London von Neumann J (1966) Theory of self-reproducing automata. In: Burks AW (ed) University of Illinois Press, Urbana, London
Zurück zum Zitat Sablik M, Theyssier G (2008) Topological dynamics of 2D cellular automata. In: CiE ’08: Proceedings of the 4th conference on computability in Europe, Springer, Berlin, Heidelberg, pp 523–532 Sablik M, Theyssier G (2008) Topological dynamics of 2D cellular automata. In: CiE ’08: Proceedings of the 4th conference on computability in Europe, Springer, Berlin, Heidelberg, pp 523–532
Zurück zum Zitat Shereshevsky MA (1993) Expansiveness, entropy and polynomial growth for groups acting on subshifts by automorphisms. Indag Math 4(2):203–210MathSciNetMATHCrossRef Shereshevsky MA (1993) Expansiveness, entropy and polynomial growth for groups acting on subshifts by automorphisms. Indag Math 4(2):203–210MathSciNetMATHCrossRef
Zurück zum Zitat Wang H (1961) Proving theorems by pattern recognition - ii. Bell Syst Tech J 40:1–42 Wang H (1961) Proving theorems by pattern recognition - ii. Bell Syst Tech J 40:1–42
Zurück zum Zitat Wolfram S (ed) (1986) Theory and applications of cellular automata. World Scientific, SingaporeMATH Wolfram S (ed) (1986) Theory and applications of cellular automata. World Scientific, SingaporeMATH
Zurück zum Zitat Wolfram S (2002) A new kind of science. Wolfram Media, Champaign, IL, USAMATH Wolfram S (2002) A new kind of science. Wolfram Media, Champaign, IL, USAMATH
Metadaten
Titel
Basic Concepts of Cellular Automata
verfasst von
Jarkko J. Kari
Copyright-Jahr
2012
Verlag
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/978-3-540-92910-9_1