Cellular automata. A volume in the Encyclopedia of Complexity and Systems Science (Q1797859)

Cellular automata (CA) are dynamical systems whose global behavior emerges from the simultaneous application at every point of a local rule with finite range. Although several variants of the model exist, they are all based on the following essential components: \begin{itemize} \item[1.] A \textit{lattice} \(\mathcal{L}\). This is a graph with vertices (the \textit{cells}) and edges representing connections between cells; it may be finite or infinite. \item[2.] A \textit{set of states} (or \textit{alphabet}) \(A\) for the cells of \(\mathcal{L}\). There are usually restrictions on this component, such as finiteness (the default) or finite dimension (for vector spaces). \item[3.] A \textit{neighborhood index} \(\mathcal{N}\) containing finitely many offsets, which determine the \textit{neighbors} of each point; such neighbors can include the point itself. \item[4.] A \textit{local rule} \(f\) which returns the next state of a point as a function of the current state of its neighbors. \end{itemize} The synchronous application of the local rule at each node determines a \textit{global function} from the set of the \textit{configurations} (global states of the lattice) into itself. Under ``classical'' hypotheses, this set is compact and metrizable, with two configurations being ``near'' if they are equal within a ``large'' distance from a predetermined ``origin'' of the lattice; and global functions are continuous, which allows to see CA as dynamical systems. Classical examples are: \begin{itemize} \item The \textit{Game of Life}, invented by John Horton Conway. The lattice is an infinite square grid; the states are ``living'' and ``dead''; the neighborhood is made of the cell and its first neighbors in each of the eight main directions. Living cells remain alive if and only if they have exactly two or exactly three living neighbors; dead cells become living if they have exactly three living neighbors. \item Stephen Wolfram's \textit{elementary CA}. The lattice is a bi-infinite line; the states are bits; the neighborhood is made of the center and the closest left and right cells. There is a standard nomenclature which encodes the local rule into a single numer between 0 and 255: the \(i\)th bit is the value of the local rule when the state of the neighborhood is the binary notation of \(i\). \end{itemize} Applications of cellular automata include modeling of populations, approximations of differential equations, and simulations of chemical reactions. They can also be employed as computational devices, and in this respect they can simulate Turing machines. The present volume of the Encyclopedia of Complexity and Systems Science, now in its second edition, provides a comprehensive overview of theoretical and practical aspects of cellular automata as models of computation and simulation and as mathematical objects of independent interest. Each chapter of the book is dedicated to a specific aspect or application of cellular automata and is authored by one or more renowned experts in the respective fields who have obtained significant results on the chapter's subject. They are all self-contained, following (with few exceptions) a common structure: \begin{itemize} \item[1.] Outline. \item[2.] Glossary. \item[3.] Definition of the subject. \item[4.] Discussion of the subject. \item[5.] Future directions. \item[6.] Bibliography. \end{itemize} Some of the entries are new in this second edition; of those, some are published here for the first time, and some have appeared in other volumes of the encyclopedia. Having all of them in a single volume is very convenient. Here is a list of the chapters with brief descriptions of their content. \begin{itemize} \item ``Cellular automata in triangular, pentagonal, and hexagonal tessellations'' by \textit{Carter Bays} (pp. 1--10). The author analyzes variants of Conway's Game of Life on different kinds of grids. The case of pentagonal grids is a remarkable addition as identical regular pentagons don't tile the plane but different non-regular pentagons can. \item ``Cellular automata in hyperbolic spaces'' by \textit{Maurice Margenstern} (pp. 11--27); new in this edition. The hyperbolic plane still admits tessellations where, however, not all vertices can have the same number of neighbors. Nevertheless, it is still possible to define CA in the hyperbolic plane, and some problems which are difficult for classical CA become much easier for hyperbolic CA. \item ``Structurally dynamic cellular automata'' by \textit{Andrew Ilachinski} (pp. 29--71). What happens if, in addition to the state, the lattice too changes according to a local rule? The author discusses several models in detail. \item ``Asynchronous cellular automata'' by \textit{Nazim Fatès} (pp. 73--92); new in this edition. Asynchronous CA still have a global clock, but each cell has a given probability of updating. It is of interest to determine how robust the rules are, that is, how much the long-term behavior remains similar to the synchronous case. \item ``Quantum cellular automata'' by \textit{Karoline Wiesner} (pp. 93--104); new in this edition. The author discusses and compares several models which adapt CA to the framework of quantum mechanics and integrate them into this framework. \item ``Reversible cellular automata'' by \textit{Kenichi Morita} (pp. 105--128); new in this edition. If the global function of a \(k\)-dimensional CA with finitely many states is bijective, then the inverse function is also a CA global function. The author illustrates several techniques to obtain reversible CA and discusses issues such as universality and simulation. \item ``Additive cellular automata'' by \textit{Burton Voorhees} (pp. 129--151). An abelian group structure on the set of states induces an abelian group structure on the configurations, and CA global functions can be group homomorphisms. The author describes such CA from the point of view of linear algebra. \item ``Cellular automata with memory'' by \textit{Ramón Alonso-Sanz} (pp. 153--183). A class of cellular automata is discussed where the next state can depend on some previous states in addition to the current one. Several variations of elementary CA are illustrated. \item ``Classification of cellular automata'' by \textit{Klaus Sutner} (pp. 185--200). The author discusses the problem of subdividing the set of cellular automata into classes according to the CA's global behavior. Both informal (such as Wolfram's) and rigorous (such as Culik and Yu's) classifications are considered and compared. \item ``Tiling problem and undecidability in cellular automata'' by \textit{Jarkko Kari} (pp. 201--219); new in this edition. This chapter contains a collection of problems about cellular automata that are algorithmically undecidable. The arguments of the proofs are based on the theory of tilings of the plane, which are in fact a ``static'' counterpart of CA. \item ``Cellular automata and groups'' by \textit{Tullio Ceccherini-Silberstein} and \textit{Michel Coornaert} (pp. 221--238). A notion of CA is given such that the alphabet and the grid can be of arbitrary cardinality, but the latter must obey a regularity condition represented by the action of a group. Links between group theory and CA theory and insights about the latter from the former are discussed. \item ``Self-replication and cellular automata'' by \textit{Gianluca Tempesti}, \textit{Daniel Mange} and \textit{André Stauffer} (pp. 239--259); new in this edition. The topic of the chapter is the ability of a CA local configuration to produce a copy of itself. The authors describe existing models and discuss approaches and techniques. \item ``Gliders in cellular automata'' by \textit{Carter Bays} (pp. 261--273). A glider in a CA is a local configuration which produces a displaced copy of itself in finitely many steps. The chapter contains several examples in different grids, inspired by the classical example of the Game of Life. \item ``Basins of attraction of cellular automata and discrete dynamical systems'' by \textit{Andrew Wuensche} (pp. 275--289); new in this edition. The author examines the behavior of CA on finite lattices, where each point ultimately reaches a cycle. \item ``Growth phenomena in cellular automata'' by \textit{Janko Gravner} (pp. 291--308); new in this edition. Considering cells as either ``occupied'' or ``unoccupied'', the author discusses if the iterates of an initial configuration are such that each cell ultimately remains in the same state. In this case, the behavior of the set of occupied cells is analyzed. \item ``Emergent phenomena in cellular automata'' by \textit{James E. Hanson} (pp. 309--321). In this chapter, several phenomena which can be observed in the evolution of CA and result from the underlying global dynamics are presented. These include the formation of blocks, the appearance of traveling particles, and the partitioning of the space into regions. \item ``Dynamics of cellular automata in noncompact spaces'' by \textit{Enrico Formenti} and \textit{Petr Kůrka} (pp. 323--335). The authors discuss CA behavior in some quotient topologies where transitions are isometries instead of chaotic maps as they are under ``classical'' hypotheses. Connections between properties of the original CA and of the induced maps are presented. \item ``Orbits of Bernoulli measures in cellular automata'' by \textit{Henryk Fukś} (pp. 337--355); new in this edition. Bernoulli measures are obtained in a standard way from measures on the family of \textit{cylinders} (configuration with a fixed finite block in common); also, CA turn Borel (in particular, Bernoulli) measures into Borel measures. This is examined for several elementary CA. \item ``Chaotic behavior of cellular automata'' by \textit{Julien Cervelle}, \textit{Alberto Dennunzio} and \textit{Enrico Formenti} (pp. 357--371); new in this edition. Several properties of dynamical systems linked to the idea of chaos are discussed in the context of CA on hypercubic grids. Links with combinatorial properties of the local rules and decidability of specific properties under special hypotheses are among the arguments presented. \item ``Ergodic theory of cellular automata'' by \textit{Marcus Pivato} (pp. 373--418). This chapter is a treatise on CA as measurable dynamical systems. Some connections with group theory are also discussed. \item ``Topological dynamics of cellular automata'' by \textit{Petr Kůrka} (pp. 419--444). This chapter is a treatise of classical theory of CA on the one-dimensional infinite grid, which shows many links between the combinatorial properties of the local rule and the dynamical properties of the global function. \item ``Control of cellular automata'' by \textit{Franco Bagnoli}, \textit{Samira El Yacoubi} and \textit{Raúl Rechtman} (pp. 445--458); new in this edition. Control theory studies how to give external input to a running system to make it reach a specific target. The authors discuss, given a CA and an initial configuration, how to make the CA reach a specific configuration, and how to make it follow a trajectory. \item ``Algorithmic complexity and cellular automata'' by \textit{Julien Cervelle} and \textit{Enrico Formenti} (pp. 459--477). The theory of Kolmogorov complexity, an uncomputable function which nevertheless has remarkable combinatorial properties, is applied to prove remarkable properties of CA. \item ``Graphs related to reversibility and complexity in cellular automata'' by \textit{Juan C. Seck-Tuoh-Mora} and \textit{Genaro J. Martínez} (pp. 479--492); new in this edition. The authors discuss applications of graph theory to the study of CA dynamics; among these, the use of de Bruijn graphs for the description of the local rule. \item ``Cellular automata as models of parallel computation'' by \textit{Thomas Worsch} (pp. 493--511). The author examines several aspects of the use of CA as computing devices. A special focus is given on time and space complexity of CA procedures, compared to those of Turing machines.. \item ``Cellular automata and language theory'' by \textit{Martin Kutrib} (pp. 513--542). The author discusses language recognition by CA and by iterative arrays. Several classes of languages are examined and compared. \item ``Evolving cellular automata'' by \textit{Martin Cenek} and \textit{Melanie Mitchell} (pp. 543--554). The chapter's subject is the construction of CA that perform specific tasks. The authors present an overview of the use of genetic algorithms in the realization of CA. \item ``Cellular automata hardware implementation'' by \textit{Georgios Ch. Sirakoulis} (pp. 555--582); new in this edition. The author analyzes models and strategies for the realization of both classical and quantum CA, and some specializations for the solutions of specific problems in physics, biology, and complex systems simulation. \item ``Firing squad synchronization problem in cellular automata'' by \textit{Hiroshi Umeo} (pp. 583--639); new in this edition. Given a line of soldiers with a general on one extreme, is there a strategy to make all soldiers fire at the same time? This article explores and compares several solutions, the number of required states, and the time required to reach the firing condition.. \item ``Universality of cellular automata'' by \textit{Jérôme Durand-Lose} (pp. 641--656). The author discusses the ability of CA to perform universal computation and to simulate every other CA. Several approaches to the latter are examined. \item ``Cellular automata modeling of physical systems'' by \textit{Bastien Chopard} (pp. 657--689). In this chapter the use of CA as models of physical systems is illustrated through a list of important examples, among these, the Ising model and the HPP and FHP lattice gas automata. Variations such as the lattice Boltzmann models are also presented. \item ``Stochastic cellular automata as models of reaction-diffusion processes'' by \textit{Olga Bandman} (pp. 691--703); new in this edition. This chapter is a short introduction to the topic. An application to the simulation of a chemical process is presented, and a hardware implementation is discussed. \item ``Phase transitions in cellular automata'' by \textit{Nino Boccara} (pp. 705--718). Situations in which the behavior of a CA changes radically according to a parameter being above or below a certain threshold are discussed. Examples include percolation, car traffic, and epidemics. \item ``Self-organized criticality in cellular automata'' by \textit{Michael Creutz} (pp. 719--732); new in this edition. The author discusses several CA whose evolution tends to reach states where changes occur at all scales, among these, sandpile automata and the Game of Life. One section is dedicated to the case of reversible CA. \item ``Identification of cellular automata'' by \textit{Andrew Adamatzky} (pp. 733--747); new in this edition. Given a collection of global transitions of a CA, one wants to infer the local rule. The author examines several approaches, including machine learning and genetic programming. \end{itemize} The average quality of the chapters is very high, with many excellent ones; all of them include rich bibliographies. The range of the topics is very broad, and researchers from many different fields can find relevant information and new ideas, or even just an introduction to the subject of cellular automata from a point of view close to their own field. It was, of course, impossible to discuss \textit{every} aspect of cellular automata theory; for example, I was a bit surprised to find no chapter on CA dynamics on subshifts, although this topic is touched in some of the existing entries. Nevertheless, this volume does an excellent job of giving an overview as broad and updated as possible on the subject of cellular automata. There are some (inevitable) typos, but none of those I stumbled upon could compromise the meaning or the understanding of the text. Summarizing, this volume is an important collection of high-quality works and an excellent reference for researchers in fields related to cellular automata as well as for newcomers to the subject. It is an important addition to the scientific library of any academic institution. The articles of this volume will be announced individually. Indexed articles: \textit{Bays, Carter}, Cellular automata in triangular, pentagonal, and hexagonal tessellations, 1-10 [Zbl 1484.68115] \textit{Margenstern, Maurice}, Cellular automata in hyperbolic spaces, 11-27 [Zbl 1484.68128] \textit{Ilachinski, Andrew}, Structurally dynamic cellular automata, 29-71 [Zbl 1484.68125] \textit{Fatès, Nazim}, Asynchronous cellular automata, 73-92 [Zbl 1484.68122] \textit{Wiesner, Karoline}, Quantum cellular automata, 93-104 [Zbl 1484.68135] \textit{Morita, Kenichi}, Reversible cellular automata, 105-128 [Zbl 1484.68129] \textit{Voorhees, Burton}, Additive cellular automata, 129-151 [Zbl 1484.68134] \textit{Alonso-Sanz, Ramón}, Cellular automata with memory, 153-183 [Zbl 1484.68112] \textit{Sutner, Klaus}, Classification of cellular automata, 185-200 [Zbl 1484.68131] \textit{Kari, Jarkko}, Tiling problem and undecidability in cellular automata, 201-219 [Zbl 1484.68126] \textit{Ceccherini-Silberstein, Tullio; Coornaert, Michel}, Cellular automata and groups, 221-238 [Zbl 1484.68117] \textit{Tempesti, Gianluca; Mange, Daniel; Stauffer, André}, Self-replication and cellular automata, 239-259 [Zbl 1484.68132] \textit{Bays, Carter}, Gliders in cellular automata, 261-273 [Zbl 1484.68116] \textit{Wuensche, Andrew}, Basins of attraction of cellular automata and discrete dynamical networks, 275-289 [Zbl 1484.68137] \textit{Gravner, Janko}, Growth phenomena in cellular automata, 291-308 [Zbl 1484.68123] \textit{Hanson, James E.}, Emergent phenomena in cellular automata, 309-321 [Zbl 1484.68124] \textit{Formenti, Enrico; Kůrka, Petr}, Dynamics of cellular automata in noncompact spaces, 323-335 [Zbl 1484.37022] \textit{Fukś, Henryk}, Orbits of Bernoulli measures in cellular automata, 337-355 [Zbl 1484.37023] \textit{Cervelle, Julien; Dennunzio, Alberto; Formenti, Enrico}, Chaotic behavior of cellular automata, 357-371 [Zbl 1484.37020] \textit{Pivato, Marcus}, Ergodic theory of cellular automata, 373-418 [Zbl 1484.37026] \textit{Kůrka, Petr}, Topological dynamics of cellular automata, 419-444 [Zbl 1484.37025] \textit{Bagnoli, Franco; El Yacoubi, Samira; Rechtman, Raúl}, Control of cellular automata, 445-458 [Zbl 1484.68113] \textit{Cervelle, Julien; Formenti, Enrico}, Algorithmic complexity and cellular automata, 459-477 [Zbl 1484.68119] \textit{Seck-Tuoh-Mora, Juan C.; Martínez, Genaro J.}, Graphs related to reversibility and complexity in cellular automata, 479-492 [Zbl 1484.37027] \textit{Worsch, Thomas}, Cellular automata as models of parallel computation, 493-511 [Zbl 1484.68136] \textit{Kutrib, Martin}, Cellular automata and language theory, 513-542 [Zbl 1484.68127] \textit{Cenek, Martin; Mitchell, Melanie}, Evolving cellular automata, 543-554 [Zbl 1484.68118] \textit{Sirakoulis, Georgios Ch.}, Cellular automata hardware implementation, 555-582 [Zbl 1484.68130] \textit{Umeo, Hiroshi}, Firing squad synchronization problem in cellular automata, 583-639 [Zbl 1484.68133] \textit{Durand-Lose, Jérôme}, Universality of cellular automata, 641-656 [Zbl 1484.68121] \textit{Chopard, Bastien}, Cellular automata modeling of physical systems, 657-689 [Zbl 1484.37021] \textit{Bandman, Olga}, Stochastic cellular automata as models of reaction-diffusion processes, 691-703 [Zbl 1484.68114] \textit{Boccara, Nino}, Phase transitions in cellular automata, 705-718 [Zbl 1484.37019] \textit{Creutz, Michael}, Self-organized criticality and cellular automata, 719-732 [Zbl 1484.68120] \textit{Adamatzky, Andrew}, Identification of cellular automata, 733-747 [Zbl 1484.68111]