Phase Transitions of Cellular Automata

We explore some aspects of phase transitions in cellular automata. We start recalling the standard formulation of the Monte Carlo approach for a discrete system. We then formulate the cellular automaton problem using simple models and illustrate different types of possible phase transitions: density phase transitions of first and second order, damage spreading, dilution of deterministic rules, asynchronism-induced transitions, synchronization phenomena, chaotic phase transitions and the influence of the topology.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Similar content being viewed by others

Symmetry and Complexity of Cellular Automata: Towards an Analytical Theory of Dynamical System

Chapter © 2013

A Lyapunov View on the Stability of Two-State Cellular Automata

Chapter © 2013

A survey of cellular automata: types, dynamics, non-uniformity and applications

Article 23 July 2018

References

  1. Bagnoli, F.: Boolean derivatives and computation of cellular automata. Int. J. Mod. Phys. C 3, 307–320 (1992). https://doi.org/10.1142/S0129183192000257ArticleMathSciNetMATHGoogle Scholar
  2. Bagnoli, F.: On damage spreading transitions. J. Stat. Mech. 85, 151–164 (1996). https://doi.org/10.1007/BF02175559MathSciNetMATHGoogle Scholar
  3. Bagnoli, F., Cecconi, F.: Synchronization of non-chaotic dynamical systems. Phys. Lett. A 282, 9–17 (2001). https://doi.org/10.1016/S0375-9601(01)00154-2ArticleMathSciNetMATHGoogle Scholar
  4. Bagnoli, F., Rechtman, R.: Synchronization and maximum Lyapunov exponents of cellular automata. Phys. Rev. E 59, R107–R1310 (1999). https://doi.org/10.1103/PhysRevE.59.R1307ArticleMATHGoogle Scholar
  5. Bagnoli, F., Rechtman, R.: Synchronization universality classes and stability of smooth coupled map lattices. Phys. Rev. E 73, 026202 (2006). https://doi.org/10.1103/PhysRevE.73.026202ArticleGoogle Scholar
  6. Bagnoli, F., Rechtman, R.: Topological bifurcations in a model society of reasonable contrarians. Phys. Rev. E 88, 062914 (2013). https://doi.org/10.1103/PhysRevE.88.062914
  7. Bagnoli, F., Baroni, L., Palmerini, P.: Synchronization and directed percolation in coupled map lattices. Phys. Rev. E. 59, 409–416 (1999). https://doi.org/10.1103/PhysRevE.59.409ArticleGoogle Scholar
  8. Bagnoli, F., Boccara, N., Rechtman, R.: Nature of phase transitions in a probabilistic cellular automaton with two absorbing states. Phys. Rev. E 63, 046116 (2001). https://doi.org/10.1103/PhysRevE.63.046116ArticleGoogle Scholar
  9. Derrida, B.: Dynamical phase transitions in spin models and automata. In: Van Beijeren, H. (ed.) Fundamental Problems in Statistical Mechanics VII, pp. 273–309. Elsevier Science Publisher, Amsterdam (1990) Google Scholar
  10. Domany, E., Kinzel, W.: Equivalence of cellular automata to Ising models and directed percolation. Phys. Rev. Lett. 53, 311–314 (1984). https://doi.org/10.1103/PhysRevLett. 53.311ArticleMathSciNetMATHGoogle Scholar
  11. Fatès, N.: Asynchronism induces second order phase transitions in elementary cellular automata. J. Cell. Autom. 4, 21–38 (2009) MathSciNetMATHGoogle Scholar
  12. Fatès, N.: A guided tour of asynchronous cellular automata. J. Cell. Autom. 9, 387–416 (2014) MathSciNetMATHGoogle Scholar
  13. Fukś, H., Fatès, N.: Local structure approximation as a predictor of second order phase transitions in asynchronous cellular automata. Nat. Comput. 14(4), 507–522 (2015) ArticleMathSciNetGoogle Scholar
  14. Grassberger, P.: On phase transitions in Schlögl’s second model. Z. Phys. B 47, 365 (1982) ArticleMathSciNetGoogle Scholar
  15. Grassberger, P.: Synchronization of coupled systems with spatiotemporal chaos. Phys. Rev. E 59, R2520–R2524 (1999). https://doi.org/10.1103/PhysRevE.59.R2520ArticleGoogle Scholar
  16. Gutowitz, H.A., Victor, J.D., Knight, B.K.: Local structure theory for cellular automata. Physica 28D, 18–48 (1987) MathSciNetMATHGoogle Scholar
  17. Henkel, M., Hinrichsen, H., Lübeck, S.: Non-Equilibrium Phase Transitions Volume 1: Absorbing Phase Transitions. Springer Science, Dordrecht (2008) Google Scholar
  18. Hinrichsen, H., Weitz, J.S., Domany, E.: An algorithm-independent definition of damage spreading, application to directed percolation. J. Stat. Phys. 88, 617–636 (1997) ArticleMATHGoogle Scholar
  19. Huang, K.: Statistical Mechanics. Wiley, New York (1963) Google Scholar
  20. Kardar, G.P.M., Zhang, Y.-C.: Dynamic scaling of growing interfaces. Phys. Rev. Lett. 56, 889–892 (1986) ArticleMATHGoogle Scholar
  21. Janssen, H.K.: On the nonequilibrium phase transition in reaction-diffusion system with an absorbing stationary state. Z. Phys. B 42, 151 (1981) ArticleGoogle Scholar
  22. Kinzel, W.: Directed percolation. In: Adler, J., Zallen, R. Deutscher, G. (eds.) Percolation Structures and Processes. Annals of the Israel Physical Society, vol. 5, p. 425 (AIP, New York, 1983) Google Scholar
  23. Kinzel, W.: Phase transition of cellular automata. Z. Phys. B 58, 229–244 (1985). https://doi.org/10.1007/BF01309255
  24. Muñoz, M.A., Hwa, T.: On nonlinear diffusion with multiplicative noise. Europhys. Lett. 41, 147–152 (1998) ArticleGoogle Scholar
  25. Tu, Y., Grinstein, G., Muñoz, M.A.: Systems with multiplicative noise: critical behavior from KPZ equation and numerics. Phys. Rev. Lett. 78, 274–277 (1997) ArticleGoogle Scholar
  26. Tomé, T., de Oliveira, M.J.: Renormalization group of the Domany-Kinzel cellular automaton. Phys. Rev. E 55, 4000–4004 (1997). https://doi.org/10.1103/PhysRevE.55.4000ArticleGoogle Scholar
  27. Watts, D.J., Strogatz, S.H.: Collective dynamics of ‘small-world’ networks. Nature 393, 440–442 (1998). https://doi.org/10.1038/30918ArticleMATHGoogle Scholar
  28. Wolfram, S.: Statistical mechanics of cellular automata. Rev. Mod. Phys. 55, 601–644 (1983). https://doi.org/10.1103/RevModPhys. 55.601ArticleMathSciNetMATHGoogle Scholar

Acknowledgements

This work was partially supported by EU projects 288021 (EINS – Network of Excellence in Internet Science) and project PAPIIT-DGAPA-UNAM IN109213.

Author information

Authors and Affiliations

  1. Department of Physics and Astronomy and CSDC, University of Florence, via G. Sansone 1, 50019, Florence, Italy Franco Bagnoli
  2. INFN, sez. Firenze, Sesto Fiorentino, Italy Franco Bagnoli
  3. Instituto de Energías Renovables, Universidad Nacional Autónoma de México, Apdo. Postal 34, 62580, Temixco, MOR, Mexico Raúl Rechtman
  1. Franco Bagnoli