nach oben

Natural Computing

Erschienen in:

27.05.2022

Cold dynamics in cellular automata: a tutorial

verfasst von: Guillaume Theyssier

Erschienen in: Natural Computing | Ausgabe 3/2022

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

This tutorial is about cellular automata that exhibit cold dynamics. By this we mean zero Kolmogorov-Sinai entropy, stabilization of all orbits, trivial asymptotic dynamics, or similar properties. These are essentially transient and irreversible dynamics, but they capture many examples from the literature, ranging from crystal growth to epidemic propagation and symmetric majority vote. A collection of properties is presented and discussed: nilpotency and asymptotic, generic or mu- variants, unique ergodicity, convergence, bounded-changeness, freezingness. They all correspond to the cold dynamics paradigm at various degrees, and we study their links and differences by key examples and results. Besides dynamical considerations, we also focus on computational aspects: we show how such cold cellular automata can still compute under their dynamical constraints, and what are their computational limitations. The purpose of this tutorial is to illustrate how the richness and complexity of the model of cellular automata are preserved under such strong constraints. By putting forward some open questions, it is also an invitation to look more closely at this cold dynamics territory, which is far from being completely understood.

Vorheriger Artikel A GIS-aided cellular automata system for monitoring and estimating graph-based spread of epidemics

Nächster Artikel A comparison of multi-objective optimization algorithms for weight setting problems in traffic engineering

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

This notion will be presented in Sect. 4.

(Enter 1987) doesn’t use the notion of \(\mu\)-nilpotence but the property \({\mu (\{c:F^\omega (c)={\overline{0}}\})=1}\). It can be shown that the two are equivalent for freezing CA in general (Salo et al. 2021, Lemma 3.6).

For the reader familiar with life-like CA, note that we use the somewhat unconventional representation of alive cells by 0 to stay consistent with Definition 7.

Aanderaa SO, Lewis HR (1974) Linear sampling and the case of the decision problem. J Symb Log 39(3):519–548. https://doi.org/10.2307/2272894MathSciNetCrossRefMATH

Akiyama S, Arnoux P (eds) (2020) Substitution and tiling dynamics: introduction to self-inducing structures. Springer International Publishing. https://doi.org/10.1007/978-3-030-57666-0

Aracena J (2008) Maximum number of fixed points in regulatory Boolean networks. Bull Math Biol 70:1398–1409MathSciNetCrossRef

Bak P, Chen K, Tang C (1990) A forest-fire model and some thoughts on turbulence. Phys Lett A 147(5):297–300. https://doi.org/10.1016/0375-9601(90)90451-SCrossRef

Balister P, Bollobás B, Przykucki M, Smith P (2016) Subcritical \({\cal{U}}\)-bootstrap percolation models have non-trivial phase transitions. Trans Am Math Soc 368(10):7385–7411. https://doi.org/10.1090/tran/6586

Laurent B (2010) Gardens of eden and amenability on cellular automata. J Eur Math Soc. https://doi.org/10.4171/jems/196CrossRefMATH

Bollobás B, Smith P, Uzzell A (2015) Monotone cellular automata in a random environment. Comb Probab Comput 24(4):687–722. https://doi.org/10.1017/S0963548315000012MathSciNetCrossRefMATH

Boyer L, Delacourt M, Poupet V, Sablik M, Theyssier G (2015) mu-limit sets of cellular automata from a computational complexity perspective. J Comput Syst Sci 81(8):1623–1647. https://doi.org/10.1016/j.jcss.2015.05.004CrossRefMATH

Boyle M, Lind D, Rudolph D (1988) The automorphism group of a shift of finite type. Trans Am Math Soc 306(1):71–71. https://doi.org/10.1090/s0002-9947-1988-0927684-2MathSciNetCrossRefMATH

Hromkovič Juraj, Schnitger Georg (1997) Communication complexity and sequential compuation. In MFCS ’97, pages 71–84, London, UK. Springer-Verlag

Capobianco S, Guillon P, Kari J (2013) Surjective cellular automata far from the Garden of Eden. Discrete Math Theoret Comput Sci vol 15, 3(3):41–60. Automata, Logic and Semantics. https://hal.inria.fr/hal-00966380

Carton O, Guillon B, Reiter F (2018) Counter machines and distributed automata. In: Cellular automata and discrete complex systems, pp 13–28. Springer International Publishing. https://doi.org/10.1007/978-3-319-92675-9_2

Ceccherini-Silberstein T, Coornaert M (2010) Cellular automata and groups. Springer, New YorkCrossRef

Chalupa J, Leath PL, Reich GR (1979) Bootstrap percolation on a Bethe lattice. J Phys C: Solid State Phys 12(1):L31–L35. https://doi.org/10.1088/0022-3719/12/1/008CrossRef

Chassaing P, Mairesse J (2011) A non-ergodic probabilistic cellular automaton with a unique invariant measure. Stoch Process Appl 121(11):2474–2487. https://doi.org/10.1016/j.spa.2011.06.009MathSciNetCrossRefMATH

Chopard B, Droz M (1998) Cellular automata modeling of physical systems. Cambridge University Press, New YorkCrossRef

Čulik K II, Pachl J, Yu S (1989) On the limit sets of cellular automata. SIAM J Comput 18(4):831–842MathSciNetCrossRef

Delacourt M, Poupet V, Sablik M, Theyssier G (2011) Directional dynamics along arbitrary curves in cellular automata. Theoret Comput Sci 412(30):3800–3821. https://doi.org/10.1016/j.tcs.2011.02.019MathSciNetCrossRefMATH

Delacourt M, de Menibus BH (2017) Characterisation of limit measures of higher-dimensional cellular automata. Theory Comput Syst 61(4):1178–1213. https://doi.org/10.1007/s00224-017-9753-1MathSciNetCrossRefMATH

Djenaoui S, Guillon P (2019)The generic limit set of cellular automata. J Cellular Automata 14(5–6):435–477. https://www.oldcitypublishing.com/journals/jca-home/jca-issue-contents/jca-volume-14-number-5-6-2019/jca-14-5-6-p-435-477/

Durrett Richard (1984) Oriented percolation in two dimensions. The Annals of Probability, 12(4). https://doi.org/10.1214/aop/1176993140

Epperlein J, Meyerovitch T (2020) Iterated minkowski sums, horoballs and north-south dynamics. arXiv:2009.09221

Fatès N (2019) Remarks on the cellular automaton global synchronisation problem: deterministic versus stochastic models. Nat Comput 18(3):429–444. https://doi.org/10.1007/s11047-018-9683-0MathSciNetCrossRef

Fuentes MA, Kuperman MN (1999) Cellular automata and epidemiological models with spatial dependence. Physica A 267(3–4):471–486CrossRef

Gács P (2001) Reliable cellular automata with self-organization. J Stat Phys 103(1/2):45–267. https://doi.org/10.1023/a:1004823720305MathSciNetCrossRefMATH

Gadouleau M (2019) On the influence of the interaction graph on a finite dynamical system. Nat Comput 19(1):15–28. https://doi.org/10.1007/s11047-019-09732-yMathSciNetCrossRef

Gadouleau M, Richard A (2016) Simple dynamics on graphs. Theoret Comput Sci 628:62–77. https://doi.org/10.1016/j.tcs.2016.03.013MathSciNetCrossRefMATH

Gajardo A, Kari J, Moreira A (2012) On time-symmetry in cellular automata. J Comput Syst Sci 78(4):1115–1126. https://doi.org/10.1016/j.jcss.2012.01.006MathSciNetCrossRefMATH

Ginosar Y, Holzman R (2000) The majority action on infinite graphs: strings and puppets. Discret Math 215(1–3):59–71. https://doi.org/10.1016/s0012-365x(99)00228-9MathSciNetCrossRefMATH

Goles E, Ollinger N, Theyssier G (2015) Introducing freezing cellular automata. In: Exploratory papers of cellular automata and discrete complex systems (AUTOMATA 2015), pp 65–73

Goles E, Maldonado D, Montealegre-Barba P, Ollinger N (2018) Fast-parallel algorithms for freezing totalistic asynchronous cellular automata. In: Cellular automata - 13th international conference on cellular automata for research and industry, ACRI 2018, Como, Italy, September 17-21, 2018, Proceedings, volume 11115 of Lecture Notes in Computer Science, pp 406–415. Springer. https://doi.org/10.1007/978-3-319-99813-8_37

Goles E, Martínez S (1990) Neural and Automata Networks: Dynamical Behavior and Applications. Kluwer Academic Publishers, Norwell, MA, USACrossRef

Goles E, Montealegre P, Wilson MRs, Theyssier G (2021) On the impact of treewidth in the computational complexity of freezing dynamics. In: 17th conference on computability in Europe, CiE 2021, volume 12813 of Lecture Notes in Computer Science, pp 260–272. Springer. https://doi.org/10.1007/978-3-030-80049-9_24

Goles E, Montealegre-Barba P, Todinca I (2013) The complexity of the bootstraping percolation and other problems. Theoret Comput Sci 504:73–82. https://doi.org/10.1016/j.tcs.2012.08.001MathSciNetCrossRefMATH

Goles-Chacc E, Fogelman-Soulie F, Pellegrin D (1985) Decreasing energy functions as a tool for studying threshold networks. Discret Appl Math 12(3):261–277MathSciNetCrossRef

Gravner J, Griffeath D (1998) Cellular automaton growth on Z2: theorems, examples, and problems. Adv Appl Math 21(2):241–304MathSciNetCrossRef

Griffeath D, Moore C (1996) Life without death is P-complete. Complex Syst 10

Guillon P, Richard G (2008) Nilpotency and limit sets of cellular automata. In: Mathematical foundations of computer science 2008, MFCS 2008, volume 5162 of Lecture Notes in Computer Science, pp 375–386. Springer. https://doi.org/10.1007/978-3-540-85238-4_30

Hedlund GA (1969) Endomorphisms and Automorphisms of the Shift Dynamical Systems. Mathematical Systems Theory 3(4):320–375MathSciNetCrossRef

Holroyd AE (2003) Sharp metastability threshold for two-dimensional bootstrap percolation. Probab Theory Relat Fields 125(2):195–224MathSciNetCrossRef

Hurd LP (1987) Formal language characterizations of cellular automaton limit sets. Complex Systems 1:69–80MathSciNetMATH

Kari J (1992) The Nilpotency Problem of One-dimensional Cellular Automata. SIAM J Comput 21:571–586MathSciNetCrossRef

Kermack WO, McKendrick AG (1927) A contribution to the mathematical theory of epidemics. Proc R Soc Lond Ser A 115(772):700–721. https://doi.org/10.1098/rspa.1927.0118CrossRefMATH

Kůrka P (2003) Topological and symbolic dynamics. Société Mathématique de France

Kůrka P, Maass A (2000) Limit sets of cellular automata associated to probability measures. J Stat Phys 100(5–6):1031–1047MathSciNetCrossRef

Kutrib M, Malcher A (2010) Cellular automata with sparse communication. Theoret Comput Sci 411(38–39):3516–3526. https://doi.org/10.1016/j.tcs.2010.05.024MathSciNetCrossRefMATH

Lathrop JI, Lutz JH, Patitz MJ, Summers SM (2011) Computability and complexity in self-assembly. Theory Comput Syst 48(3):617–647MathSciNetCrossRef

Lind D, Marcus B (1995) An introduction to symbolic dynamics and coding. Cambridge University Press, CambridgeCrossRef

Lind DA (1984) Applications of ergodic theory and sofic systems to cellular automata. Physica D 10(1–2):36–44. https://doi.org/10.1016/0167-2789(84)90246-XMathSciNetCrossRefMATH

Mac Culloch WS, Pitts WS (1943) A logical calculus of the ideas immanent in nervous activity. Bull Math Bio Phys 5:113–115MathSciNet

Mairesse J, Marcovici I (2014) Around probabilistic cellular automata. Theoret Comput Sci 559:42–72. https://doi.org/10.1016/j.tcs.2014.09.009MathSciNetCrossRefMATH

Marcovici I, Sablik M, Taati S (2019) Ergodicity of some classes of cellular automata subject to noise. Electron J Probab. https://doi.org/10.1214/19-EJP297MathSciNetCrossRefMATH

Hellouin De Menibus B, Salo V, Theyssier G (2018) Characterizing asymptotic randomization in abelian cellular automata. Ergodic Theory Dyn Syst 40(4):923–952. https://doi.org/10.1017/etds.2018.75MathSciNetCrossRefMATH

Menibus BHD, Sablik M (2016) Characterization of sets of limit measures of a cellular automaton iterated on a random configuration. Ergodic Theory Dyn Syst 38(2):601–650. https://doi.org/10.1017/etds.2016.46MathSciNetCrossRefMATH

Meunier P, Regnault D, Woods D (2020) The program-size complexity of self-assembled paths. In: Konstantin M, Yury M, Madhur T, Gautam K, Julia C (eds) Proccedings of the 52nd annual ACM SIGACT symposium on theory of computing, STOC 2020, Chicago, IL, USA, June 22–26, 2020, pp 727–737. ACM. https://doi.org/10.1145/3357713.3384263

Meunier P, Woods D v(2017) The non-cooperative tile assembly model is not intrinsically universal or capable of bounded turing machine simulation. In: Hatami H, McKenzie P, King V, (eds) Proceedings of the 49th annual ACM SIGACT symposium on theory of computing, STOC 2017, Montreal, QC, Canada, June 19–23, 2017, pp 328–341. ACM. https://doi.org/10.1145/3055399.3055446

Milnor J (1985) On the concept of attractor. Commun Math Phys 99(2):177–195. https://doi.org/10.1007/bf01212280MathSciNetCrossRefMATH

Miyamoto M (1979) An equilibrium state for a one-dimensional life game. J Math Kyoto Univ 19(3):525–540MathSciNetMATH

Morita K (2008) Reversible computing and cellular automata-a survey. Theoret Comput Sci 395(1):101–131. https://doi.org/10.1016/j.tcs.2008.01.041MathSciNetCrossRefMATH

Morris R (2017) Bootstrap percolation, and other automata. Eur J Comb 66:250–263. https://doi.org/10.1016/j.ejc.2017.06.024MathSciNetCrossRefMATH

Morris R (2017) Monotone cellular automata, pp 312–371. London Mathematical Society Lecture Note Series. Cambridge University Press. https://doi.org/10.1017/9781108332699.008

Ollinger N, Theyssier G (2022) Freezing, bounded-change and convergent cellular automata. Discrete Math Theoret Comput Sci https://doi.org/10.46298/dmtcs.5734

Patitz MJ (2013) An introduction to tile-based self-assembly and a survey of recent results. Nat Comput 13(2):195–224. https://doi.org/10.1007/s11047-013-9379-4MathSciNetCrossRefMATH

Pivato Marcus (2009) Ergodic theory of cellular automata. In Encyclopedia of Complexity and Systems Science, pages 2980–3015. Springer, New York, NY. https://doi.org/10.1007/978-0-387-30440-3_178

Robert F (1986) Discrete iterations: a metric study, volume 6 of Series in Computational Mathematics. Springer

Rogers H (1967) Theory of recursive functions and effective computability. MIT Press, LondonMATH

Salo Ville (2012) On nilpotency and asymptotic nilpotency of cellular automata. In AUTOMATA & JAC 2012, volume 90 of EPTCS, pages 86–96. URL: 10.4204/EPTCS.90.7

Salo V (2017) Strict asymptotic nilpotency in cellular automata. In: Cellular automata and discrete complex systems. Springer International Publishing, Cham, pp 3–15

Salo V (2019) No tits alternative for cellular automata. Groups Geom Dyn 13(4):1437–1455. https://doi.org/10.4171/ggd/529MathSciNetCrossRefMATH

Salo V, Guillaume T, Ilkka T (2021) Bootstrap percolation and cellular automata. arXiv:2110.00656

Salo V, Törmä I (2021) Nilpotent endomorphisms of expansive group actions. Int J Algebra Comput 31(03):393–452. https://doi.org/10.1142/s021819672150020xMathSciNetCrossRefMATH

Toom AL (1980) Stable and attractive trajectories in multicomponent systems. Multicompon Random Syst 6:549–575MathSciNetMATH

Törmää I (2015) A uniquely ergodic cellular automaton. J Comput Syst Sci 81(2):415–442. https://doi.org/10.1016/j.jcss.2014.10.001MathSciNetCrossRefMATH

Törmää I (2021) Generically nilpotent cellular autom, 2021 arXiv:2108.12925

Ulam SM (1970) On some mathematical problems connected with patterns of growth of figures. In: Burks AW (ed) Essays on cellular automata. University of Illinois Press, pp 219–231

van Enter ACD (1987) Proof of straley’s argument for bootstrap percolation. J Stat Phys 48(3–4):943–945. https://doi.org/10.1007/bf01019705MathSciNetCrossRefMATH

Vollmar R (1981) On cellular automata with a finite number of state changes. In: Parallel processes and related automata/parallele prozesse und damit zusammenhängende Automaten, volume 3 of Computing Supplementum, pp 181–191. Springer Vienna. https://doi.org/10.1007/978-3-7091-8596-4_13

Walters P (1981) An introduction to ergodic theory. Graduate texts in mathematics. Springer, New York

Winfree E (1998) Algorithmic self-assembly of DNA. PhD thesis, California Institute of Technology

Wolf-Gladrow DA (2000) Lattice gas cellular automata and lattice Boltzmann models. Springer, Berlin. https://doi.org/10.1007/b72010CrossRefMATH

Titel: Cold dynamics in cellular automata: a tutorial
verfasst von: Guillaume Theyssier
Publikationsdatum: 27.05.2022
Verlag: Springer Netherlands
Erschienen in: Natural Computing / Ausgabe 3/2022
Print ISSN: 1567-7818
Elektronische ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-022-09886-2

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 3/2022

MRT-lattice Boltzmann hybrid model for the double diffusive mixed convection with thermodiffusion effect

A GIS-aided cellular automata system for monitoring and estimating graph-based spread of epidemics

A comparison of multi-objective optimization algorithms for weight setting problems in traffic engineering

Time discretization in the time-continuous pedestrian dynamics model SigmaEva

Heuristic search of (semi-)bent functions based on cellular automata

Preface

Premium Partner