Cellular automata

• Dr. Hector Zenil, School of Biomedical Engineering and Imaging Sciences, King's College London, U.K.

• Dr. Genaro J. Martinez, Instituto Politecnico Nacional, Mexico City, Mexico

A cellular automaton (CA) is, in its classical form, a deterministic dynamical system that evolves in discrete time on a regular discrete lattice. It consists of cells, each of which takes a value from a finite set of states. At each time step, the same local update rule is applied synchronously to every cell. The new state depends on the states at a fixed, finite set of relative positions called its neighborhood, which may include the cell itself. A configuration specifies the states of all cells at a particular time. Classical theory often considers an infinite lattice, while computer simulations generally use finite regions with specified boundary conditions (Kari, 2005; Dennunzio, Formenti, & Kůrka, 2012).

Some cellular automata are computationally universal: with suitable encodings and initial configurations, they can simulate a universal Turing machine. This is a property of particular rules, not of every cellular automaton. Their local, parallel organization and the diversity of their space-time patterns make cellular automata useful both as abstract computational models and as models of spatially extended physical and biological processes (Chopard & Droz, 1998; Cook, 2004; Deutsch & Dormann, 2005).

Two-dimensional Cellular Automata and Neighborhoods

The early history of cellular automata includes Stanislaw Ulam's investigations of discrete growth patterns and John von Neumann's work on self-reproducing automata. Ulam's paper On some mathematical problems connected with patterns of growth in figures documents his study of growth patterns (Ulam, 1962). Von Neumann, drawing on Ulam's suggestion to use a discrete cellular setting, developed a construction capable of universal computation and self-reproduction (Kari, 2005). His work was published posthumously in Theory of Self-Reproducing Automata, edited and completed by Arthur W. Burks (von Neumann, 1966). Ulam's growth investigations and von Neumann's self-reproducing construction represent distinct contributions. Nils Aall Barricelli also conducted early numerical experiments on artificial evolution (Barricelli, 1962).

Two common neighborhoods on a square lattice are the von Neumann and Moore neighborhoods. At radius one, the von Neumann neighborhood contains the four orthogonally adjacent cells, together with the central cell when it is included in the update neighborhood. The Moore neighborhood additionally includes the four diagonally adjacent cells. Thus, these neighborhoods contain five and nine sites, respectively, when the central cell is counted, or four and eight surrounding neighbors when it is excluded. Stating this convention avoids ambiguity (Kari, 2005).

Von Neumann's construction used 29 states and the five-site von Neumann neighborhood. Edgar F. Codd subsequently described an eight-state system with the same neighborhood that retained computation and construction universality (Codd, 1968). Christopher G. Langton's eight-state self-reproducing loops also use this neighborhood, but their capacity for self-reproduction does not require the universal construction capability of the earlier designs (Langton, 1984).

John Conway's Game of Life is a two-state, two-dimensional cellular automaton using the eight surrounding cells of the Moore neighborhood. Martin Gardner introduced it to a wide audience in 1970 (Gardner, 1970). A dead cell becomes alive if it has exactly three live neighbors; a live cell survives if it has two or three live neighbors. This rule, conventionally written B3/S23, supports persistent structures, moving patterns called gliders, and constructions capable of universal computation. The latter requires deliberately arranged configurations, rather than arising from every initial pattern (Gardner, 1970; Wolfram, 2002).

Other examples illustrate the diversity of two-dimensional rules and neighborhoods. The years below identify the cited publications, not necessarily the dates when the rules were first conceived.

• Critters: a two-state reversible block cellular automaton described by Toffoli and Margolus (1987). It uses alternating partitions into \(2\times2\) blocks, known as the Margolus neighborhood, rather than an ordinary fixed neighborhood updated independently at each site.
• Brian's Brain: a three-state rule associated with Brian Silverman and described by Toffoli and Margolus (1987). It uses the Moore neighborhood and distinguishes quiescent, firing, and refractory states.
• Life Without Death: a two-state Moore-neighborhood rule in which dead cells become alive when exactly three neighbors are alive, while live cells never die. Griffeath and Moore (1996) proved a P-completeness result for its finite-time prediction problem.
• Larger than Life: a family of two-state rules extending Life to larger neighborhoods and birth and survival thresholds, studied in Kellie M. Evans's dissertation (Evans, 1996). It is a family of rules rather than a single rule. Evans's later account credits David Griffeath with proposing the family in the early 1990s (Evans, 2016).
• Beehive: a three-state rule supporting self-reproduction through glider collisions (Wuensche, 2004). Its two-dimensional version uses six neighbors on a hexagonal tiling, excluding the central cell. The same paper also examines a three-dimensional version with six neighbors on a cubic lattice; the three-dimensional neighborhood is not a hexagonal tiling.
• Spiral rule: a three-state rule on a hexagonal tiling, with the six adjacent cells and the central cell included in the update neighborhood. It supports spiral glider guns and other interacting structures (Wuensche & Adamatzky, 2006).
• Diffusion Rule: a two-state Moore-neighborhood rule with birth at two live neighbors and survival at seven, conventionally written B2/S7. Martínez, Adamatzky, and McIntosh (2010) studied its mobile and stationary localized patterns and their interactions. The name refers to diffusion-like pattern dynamics, not to a general derivation of the physical diffusion equation.
• Cellular automata on Penrose tilings: Goucher (2012) described a four-state automaton supporting gliders on aperiodic tilings. Its generalized neighborhood includes tiles sharing a vertex. A Penrose tiling specifies the underlying geometry, not a unique cellular-automaton rule.
• T0347: an eight-state reversible elementary triangular partitioned cellular automaton studied by Morita (2016). Each triangular cell has three binary parts, and information is exchanged with its three edge-adjacent neighbors. The model supports gliders, glider guns, and universal reversible logic.

Cellular automata can also be defined on tilings of hyperbolic space. Margenstern (2008) gave constructions for simulating cellular automata on several hyperbolic grids, including grids in two and three dimensions. This work concerns a class of constructions, rather than one uniquely specified "hyperbolic universal rule."

Konrad Zuse explored a different application of cellular ideas to physics. His book Rechnender Raum appeared in German in 1969 and in English translation as Calculating Space in 1970. Zuse proposed that physical processes might have a discrete computational basis. This was a proposal about the foundations of physics, not an established result that the universe is a cellular automaton. A newly typeset edition of the MIT translation, prepared by Adrian German and Hector Zenil, appeared in A Computable Universe (Zuse, 1970; Zenil, 2012).

Elementary Cellular Automata

In the 1980s, Stephen Wolfram systematically investigated one-dimensional, two-state, nearest-neighbor cellular automata, generally called elementary cellular automata (ECA). Each cell takes one of two values, usually 0 or 1, and its next state depends on its own state and those of its immediate left and right neighbors. Successive configurations can be displayed as rows in a two-dimensional space-time diagram (Wolfram, 1983, 1994, 2002).

These systems exhibit a wide range of behavior despite their small rule tables. For example, Rule 30 can generate irregular patterns with statistical properties resembling randomness from simple initial conditions. Such behavior should be distinguished from an external source of randomness: the evolution remains deterministic (Wolfram, 1983, 2002).

Rule-naming convention and higher dimensions

Wolfram's enumeration of ECA assigns an output to each of the eight neighborhood configurations, conventionally ordered as 111, 110, 101, 100, 011, 010, 001, and 000. The resulting sequence of outputs is read as an eight-bit binary number. Thus, the output string 00000010 defines Rule 2. There are \(2^3=8\) possible neighborhood configurations and therefore \(2^8=256\) distinct rule tables before identifying any equivalences under reflection or state relabeling (Wolfram, 1983, 1994).

More generally, a deterministic rule with \(k\) states and \(n\) specified neighborhood sites has \(k^n\) possible local inputs and \(k^{k^n}\) possible rule tables, if no further constraints are imposed. Restrictions such as totalism, symmetry, or conservation reduce the set of allowed rules.

A CA defined on a \(d\)-dimensional lattice has a space-time representation with \(d\) spatial coordinates and one time coordinate. This does not change the spatial dimension of the automaton: ECA remain one-dimensional, and Life remains two-dimensional. Higher-dimensional lattices, larger state sets, and different neighborhoods provide additional modeling possibilities. Hyperbolic and aperiodic tilings extend the underlying geometry beyond the usual rectangular lattice (Margenstern, 2008; Goucher, 2012).

Types of boundary conditions

An infinite lattice has no outer boundary. A finite simulation, however, must specify how the update rule is evaluated near its edges. Boundary choices can affect propagation, conservation, and long-term behavior, so they form part of the model specification. The terminology below is not completely standardized; the implementation should be stated explicitly (Chopard & Droz, 1998; Toffoli & Margolus, 1987).

Periodic boundary conditions

Opposite edges are identified. A one-dimensional array becomes a ring, and a rectangular two-dimensional array becomes a torus. Patterns leaving one side reenter from the opposite side. This removes a distinguished outer edge but can introduce finite-size effects and interactions between periodic copies of a pattern.

Fixed boundary conditions

Boundary cells, or the exterior values used when evaluating boundary updates, are held at prescribed states. These are distinct implementation choices and should not be left implicit. The prescribed state is often a quiescent state.

Reflective boundary conditions

Values outside the simulated region are obtained by reflecting nearby interior values. In particle-based models, reflection may instead reverse the relevant velocity components. The precise reflection rule depends on the model; it is not automatically equivalent to a particular differential-equation boundary condition.

Absorbing boundary conditions

The boundary is designed to remove outgoing activity or particles. Fixing exterior cells to a quiescent state is one possible implementation, but it does not guarantee reflection-free absorption for every cellular-automaton rule.

Open boundary conditions

The simulated region can exchange activity or particles with an exterior environment. A complete specification gives the rules for inflow, outflow, or externally imposed states. An "open" boundary cannot simply leave required neighborhood inputs undefined.

Cellular automata as models of physics and their applications

Reversibility

A cellular automaton is reversible when its global update map is bijective: every configuration has exactly one predecessor. For a classical finite-state CA on the full configuration space of an infinite regular lattice, the inverse of a bijective cellular automaton is also a cellular automaton. Its inverse neighborhood need not be the same size as the original neighborhood. These facts are connected to the Curtis-Hedlund-Lyndon characterization of cellular automata as continuous maps commuting with lattice translations (Kari, 2005; Ceccherini-Silberstein & Coornaert, 2010).

Edward Fredkin, Tommaso Toffoli, Norman Margolus, and other researchers developed reversible computational models and investigated their relationship to physics. Fredkin's 1990 paper presents an informational model based on reversible universal cellular automata; it should not be treated as the first introduction of reversibility in cellular-automaton theory (Fredkin, 1990; Toffoli & Margolus, 1987).

Configurations without predecessors are called Garden of Eden configurations. For classical cellular automata on \(\mathbb{Z}^d\), the Garden of Eden theorem of Moore and Myhill states that surjectivity is equivalent to pre-injectivity. Pre-injectivity means that two configurations differing at only finitely many sites cannot have the same image unless they are identical. Surjectivity alone does not imply reversibility: a configuration can have more than one predecessor (Ceccherini-Silberstein & Coornaert, 2010).

Reversibility is decidable for one-dimensional classical cellular automata. In two and higher spatial dimensions, it is undecidable in general: no algorithm can decide reversibility for every finite rule description on the infinite lattice (Kari, 1990, 2005). This result does not apply to a single fixed finite array, whose finite configuration graph can in principle be exhaustively examined.

Statistical mechanics, emergent phenomena and other applications

Cellular automata provide discrete models in which microscopic rules can be studied in relation to collective behavior. Lattice-gas cellular automata represent particles moving and colliding locally. The Frisch-Hasslacher-Pomeau model demonstrated how suitable lattice symmetries and collision rules can yield hydrodynamic behavior described by the Navier-Stokes equations in an appropriate macroscopic limit. The continuum description is a limiting approximation, not an exact identity at every lattice scale (Frisch, Hasslacher, & Pomeau, 1986).

Cellular automata and related lattice models have been applied to statistical mechanics, transport, and other physical processes (Chopard & Droz, 1998; Toffoli & Margolus, 1987). Their use in the study of complex systems and artificial life is discussed by Boccara (2004) and in the volume edited by Langton (1997). Biological applications include growth, cell interactions, swarming, tissue development, and excitable-media pattern formation (Deutsch & Dormann, 2005).

Quantum cellular automata extend local discrete dynamics to quantum systems. An early example is Meyer's work connecting quantum cellular automata to quantum lattice gases (Meyer, 1996). This research should be distinguished from Gerard 't Hooft's cellular-automaton interpretation of quantum mechanics, which proposes an underlying deterministic description of quantum phenomena ('t Hooft, 2016).

The Nagel-Schreckenberg model is a stochastic cellular automaton for freeway traffic (Nagel & Schreckenberg, 1992). Cellular models have also been applied to urban land-use dynamics (White & Engelen, 1993). These applications generally add domain-specific assumptions and require comparison with observations; the presence of visually plausible patterns is not by itself evidence that a model accurately describes a natural system.

The algebraic and group-theoretic study of cellular automata addresses questions including reversibility, surjectivity, and the relationship between local rules and global maps (Ceccherini-Silberstein & Coornaert, 2010). Image-processing applications are discussed by Toffoli and Margolus (1987). Cellular automata have also been proposed for pseudorandom generation and cryptographic constructions (Wolfram, 1986). Irregular-looking output alone does not establish cryptographic security.

Cellular automata as models of computation

Computability and reachability

Turing universality means that a cellular automaton can simulate a universal Turing machine under a specified encoding. Intrinsic universality is a stronger simulation requirement: a CA must be able to reproduce the space-time dynamics of any CA in the relevant class through suitable local encodings, grouping of cells, and rescaling of time, with the precise definition depending on the simulation framework. The class being simulated, such as automata of a fixed spatial dimension, must be specified (Kari, 2005; Dennunzio, Formenti, & Kůrka, 2012).

Cellular automata have been studied as parallel models of computation, language recognition, and decision problems (Culik II, Hurd, & Yu, 1990). Reachability asks whether a specified configuration or pattern can be obtained from an initial condition after some number of updates. For infinite configurations, a decision problem must specify how inputs and target events are finitely described. Reversibility provides a unique inverse evolution but does not automatically make all reachability questions decidable. On a fixed finite array, reachability can be decided by following the orbit until the target is reached or a configuration repeats.

Reliable computation in the presence of local errors is another important research direction. Gács (1986) constructed cellular-automaton mechanisms for reliable computation despite noise, showing that fault tolerance can be investigated within locally interacting systems.

Dynamical systems, logic and circuits

For a deterministic cellular automaton on a finite array, every trajectory eventually enters a cycle, with a fixed point as the special case of a cycle of length one. An attractor basin consists of configurations that eventually reach the same cycle. Wuensche (1999) investigated relationships among attractor-basin structure, space-time patterns, and measures computed from local rules. The dynamics on an infinite lattice need not become periodic.

Moving localized patterns can represent signals, and their interactions can implement logical operations. Martínez, Adamatzky, and McIntosh (2006) studied glider collisions and logical gates in Rule 54. Martínez, Adamatzky, Stephens, and Hoeflich (2011) studied cellular-automaton supercolliders, including interactions among gliders circulating on rings. Constructing a particular logic gate should be distinguished from proving a complete universality result for a rule.

Continuous-valued extensions include fuzzy cellular automata, in which Boolean states and operations are replaced by graded values and corresponding update functions. Flocchini, Geurts, Mingarelli, and Santoro (2000), for example, studied convergence and aperiodicity in a fuzzy version of Rule 90. Such models extend the classical finite-state definition rather than being identical to it.

Wolfram's principles of Computational Irreducibility and Equivalence

Cellular automata illustrate how complex global behavior can emerge from simple local rules. They also provide concrete settings for investigating limits on prediction and the relationship between a system's description and the computation needed to determine its behavior.

Wolfram's idea of computational irreducibility, discussed in his work on cellular automata and developed in A New Kind of Science, concerns computations whose detailed outcomes cannot generally be obtained substantially more efficiently than by carrying out the computation itself (Wolfram, 1985, 2002). Its application depends on what is being predicted and on the allowed computational resources; it is not a theorem that every observable of a complex-looking CA requires complete step-by-step simulation.

Israeli and Goldenfeld (2006) showed how coarse-graining can produce simpler descriptions of cellular-automaton evolution. A coarse observable can therefore be predictable even when microscopic details remain difficult to predict. Sutner (2013) and Zwirn and Delahaye (2013) examined related questions using recursion theory and formal approaches to unpredictability. Zenil, Soler-Toscano, and Joosten (2012) investigated empirical approaches to computational irreducibility using small Turing machines; that experiment was not a study of cellular automata specifically.

Matthew Cook proved that Rule 110 supports universal computation, confirming an earlier conjecture by Wolfram (Cook, 2004; Wolfram, 2002). Cook's construction uses suitably arranged patterns and periodic backgrounds, so the initial-condition convention matters when stating the result.

Wolfram's Principle of Computational Equivalence proposes that systems whose behavior is not obviously simple commonly exhibit equivalent computational sophistication (Wolfram, 2002). It is a broad proposed principle, not a proved classification theorem for all cellular automata. Riedel and Zenil (2018) investigated reprogramming and emulation between rules using finite encodings and rescalings. Their cross-class emulation results provide evidence about computational relationships that are not captured by visual behavioral classes alone; they do not establish that every cellular automaton is universal.

Classification of Cellular Automata

Wolfram proposed four broad behavioral classes based on the evolution of cellular automata, typically from disordered initial conditions (Wolfram, 1984, 2002):

• Class 1: Evolution tends toward a spatially homogeneous state.
• Class 2: Evolution tends toward stable or periodically repeating structures.
• Class 3: Evolution produces irregular, apparently random or chaotic patterns.
• Class 4: Evolution produces interacting localized structures and other complicated persistent or long-lived patterns.

These are heuristic descriptions. Their application depends on initial conditions, observation time, boundary conditions, and how behavior is measured. Rule 30 is commonly associated with Class 3, while Rule 110 and the Game of Life are commonly associated with Class 4. Membership in a visual class is not itself a proof of a rule's computational power.

Quantitative approaches to classification include statistical measures, attractor-basin analysis, compression, and approximations to algorithmic complexity (Li & Packard, 1990; Wuensche, 1999; Zenil, 2010; Zenil & Villarreal-Zapata, 2013). One useful distinction is between measures calculated directly from rule tables and measures calculated from observed evolution. Langton's lambda parameter is a rule-table measure: relative to a designated quiescent state, it records the fraction of neighborhood inputs whose outputs are not that state. It does not uniquely determine the dynamics (Langton, 1990).

Limitations

There are rigorous classifications for restricted classes and selected properties, but no general algorithm decides every nontrivial dynamical question about cellular automata. Particular problems, including reversibility in dimension two or higher and several questions about long-term dynamics, are undecidable. Such results must be stated for specific properties and domains rather than used to claim that every possible classification is undecidable (Kari, 2005).

Methods based on finite observations have additional limitations: they can miss long transients or rare initial conditions and can confuse finite-size effects with properties of an infinite system. Rule-table parameters avoid running the system but may omit information needed to distinguish different dynamics. Both approaches are useful when their assumptions and scope are stated.

Mean field theory (MFT)

Mean field theory approximates cellular-automaton dynamics by replacing spatially dependent interactions with averages. A common approximation treats neighboring states as independent samples with specified densities. This yields equations for average state densities or other coarse quantities, but neglects spatial correlations and can miss structures such as gliders, interfaces, and correlated domains. More detailed approximations can retain information about small groups of cells (Boccara, 2004; Chopard & Droz, 1998).

Entropy and lossless compression

Entropy measures characterize distributions, such as the frequencies of states or blocks in an evolving pattern. Practical lossless compressors detect particular forms of regularity and can be used as computable proxies for description length. Kolmogorov complexity instead concerns the length of a shortest program producing an object and is uncomputable in general. A compressed representation supplies an upper bound, up to decoding overhead, rather than an exact value of Kolmogorov complexity. Poor compression by one algorithm is therefore not proof of algorithmic randomness (Zenil, 2010; Zenil & Villarreal-Zapata, 2013).

Reprogrammability studies add a complementary perspective: two rules with different typical visual behavior may nevertheless be related by a suitable encoding or simulation. Riedel and Zenil (2018) examined these relationships across behavioral classes.

Sensitivity and perturbation analysis

Sensitivity studies compare the evolution of initial configurations that differ by a controlled perturbation. For finite binary configurations, Hamming distance counts the differing cells. Gray-code ordering provides a way to enumerate initial configurations so that successive strings differ in exactly one bit; it is an ordering, not a distance measure in itself (Zenil, 2010).

Damage-spreading measures and Lyapunov-like quantities describe aspects of how perturbations propagate or change under the dynamics. Their interpretation depends on the metric, the initial-condition distribution, and whether one measures the number of damaged sites or the speed at which a disturbance spreads (Dennunzio, Formenti, & Kůrka, 2012).

Subclasses of Cellular Automata

Totalistic

For numerically labeled states, a totalistic rule depends only on the sum of the states in its specified neighborhood, rather than on their arrangement. If the neighborhood contains a binary cell and its two nearest neighbors, the sum can be 0, 1, 2, or 3. Assigning a binary output to each sum gives \(2^4=16\) totalistic rules within that radius-one binary setting (Wolfram, 1983, 2002).

An outer-totalistic rule treats the central cell separately: its output depends on the central cell's current state and on the sum of the surrounding neighbors. This differs from depending only on a sum that includes the central cell. Conway's Game of Life is outer-totalistic. Binary outer-totalistic rules on the radius-one Moore neighborhood are commonly called Life-like rules. In B/S notation, B lists the neighbor counts that cause birth and S lists the counts that allow survival.

For more than two states, dependence on the counts of each state is a broader permutation-invariant condition than dependence only on their numerical sum. Wuensche's k-totalistic formulation uses these state counts, so it should not be conflated with the numerical-sum definition (Wuensche, 2004).

Stochastic Cellular Automata

Stochastic cellular automata use probabilistic local updates conditioned on neighborhood states. In a common formulation, cells use conditionally independent random choices at each time step. A complete model specifies the transition probabilities and any correlations in the randomness. The Nagel-Schreckenberg traffic model is a prominent application (Nagel & Schreckenberg, 1992).

Continuous-valued and reaction-diffusion variants

Some extensions retain discrete space and time but allow continuous state values. Fuzzy cellular automata are one example (Flocchini, Geurts, Mingarelli, & Santoro, 2000). They lie outside the strict finite-state definition.

Reaction-diffusion equations are usually continuous-space, continuous-time models, although discrete lattice systems can approximate them or reproduce selected qualitative features. Turing's theory of morphogenesis is a classic reaction-diffusion approach to biological pattern formation (Turing, 1952). Excitable chemical systems, including the Belousov-Zhabotinsky reaction, have also motivated discrete models. A cellular-automaton analogy and a quantitatively validated approximation are different kinds of model (Deutsch & Dormann, 2005).

Non-uniform Cellular Automata

Non-uniform cellular automata allow the local update rule to depend on the cell's position. This relaxes the spatial uniformity of the classical definition and permits heterogeneous systems. It is distinct from asynchronous updating, which changes when cells are updated rather than necessarily changing their local rules.

Lattice Gas Automata

Lattice-gas cellular automata encode local particle populations or occupancies and evolve through propagation and collision steps. In common finite-state formulations, the combined update is itself a cellular automaton. Appropriate collision rules conserve quantities such as particle number and momentum. Reproducing a particular continuum equation additionally requires suitable symmetries, scaling assumptions, and parameter regimes (Frisch, Hasslacher, & Pomeau, 1986; Chopard & Droz, 1998).

Non-square lattice/grid

Cellular automata can be defined on triangular and hexagonal lattices as well as rectangular ones. Extensions also use aperiodic tilings, hyperbolic grids, and graphs. In each case, the adjacency relation and local update convention must be specified. Results proved for classical translation-invariant automata on \(\mathbb{Z}^d\) cannot automatically be transferred to arbitrary graphs or tilings (Margenstern, 2008; Goucher, 2012; Morita, 2016).

References

• Barricelli, N. A. (1962). Numerical testing of evolution theories. Acta Biotheoretica, 16, 69-98. DOI.

• Boccara, N. (2004). Modeling Complex Systems. Springer. ISBN 978-0-387-40462-2.

• Ceccherini-Silberstein, T., & Coornaert, M. (2010). Cellular Automata and Groups. Springer. DOI.

• Chopard, B., & Droz, M. (1998). Cellular Automata Modeling of Physical Systems. Cambridge University Press. DOI.

• Codd, E. F. (1968). Cellular Automata. Academic Press.

• Cook, M. (2004). Universality in elementary cellular automata. Complex Systems, 15(1), 1-40. DOI.

• Culik II, K., Hurd, L. P., & Yu, S. (1990). Computation theoretic aspects of cellular automata. Physica D: Nonlinear Phenomena, 45(1-3), 357-378. DOI.

• Dennunzio, A., Formenti, E., & Kůrka, P. (2012). Cellular automata dynamical systems. In G. Rozenberg, T. Bäck, & J. N. Kok (Eds.), Handbook of Natural Computing (pp. 25-75). Springer. DOI.

• Deutsch, A., & Dormann, S. (2005). Cellular Automaton Modeling of Biological Pattern Formation: Characterization, Applications, and Analysis. Birkhäuser. DOI.

• Evans, K. M. (1996). Larger than Life: It's So Nonlinear. Ph.D. dissertation, University of Wisconsin-Madison. Author's dissertation page.

• Evans, K. M. (2016). Larger than Life. In A. Adamatzky & G. J. Martínez (Eds.), Designing Beauty: The Art of Cellular Automata. Springer. DOI.

• Flocchini, P., Geurts, F., Mingarelli, A., & Santoro, N. (2000). Convergence and aperiodicity in fuzzy cellular automata: Revisiting rule 90. Physica D: Nonlinear Phenomena, 142(1-2), 20-28. DOI.

• Fredkin, E. (1990). An informational process based on reversible universal cellular automata. Physica D: Nonlinear Phenomena, 45(1-3), 254-270. DOI.

• Frisch, U., Hasslacher, B., & Pomeau, Y. (1986). Lattice-gas automata for the Navier-Stokes equation. Physical Review Letters, 56(14), 1505-1508. DOI.

• Gács, P. (1986). Reliable computation with cellular automata. Journal of Computer and System Sciences, 32(1), 15-78. Author's copy.

• Gardner, M. (1970). Mathematical games: The fantastic combinations of John Conway's new solitaire game "Life". Scientific American, 223(4), 120-123. DOI.

• Goucher, A. P. (2012). Gliders in cellular automata on Penrose tilings. Journal of Cellular Automata, 7(5-6), 385-392. Publisher's record.

• Griffeath, D., & Moore, C. (1996). Life without death is P-complete. Complex Systems, 10, 437-447. Author's publication page.

• Israeli, N., & Goldenfeld, N. (2006). Coarse-graining of cellular automata, emergence, and the predictability of complex systems. Physical Review E, 73(2), 026203. DOI.

• Kari, J. (1990). Reversibility of 2D cellular automata is undecidable. Physica D: Nonlinear Phenomena, 45(1-3), 379-385.

• Kari, J. (2005). Theory of cellular automata: A survey. Theoretical Computer Science, 334(1-3), 3-33. DOI.

• Langton, C. G. (1984). Self-reproduction in cellular automata. Physica D: Nonlinear Phenomena, 10(1-2), 135-144. DOI.

• Langton, C. G. (1990). Computation at the edge of chaos: Phase transitions and emergent computation. Physica D: Nonlinear Phenomena, 42(1-3), 12-37. DOI.

• Langton, C. G. (Ed.). (1997). Artificial Life: An Overview. MIT Press. Paperback edition; originally published in hardcover in 1995. Publisher's record.

• Li, W., & Packard, N. (1990). The structure of the elementary cellular automata rule space. Complex Systems, 4, 281-297. Full text.

• Margenstern, M. (2008). A uniform and intrinsic proof that there are universal cellular automata in hyperbolic spaces. Journal of Cellular Automata, 3(2), 157-180. Publisher's record.

• Martínez, G. J., Adamatzky, A., & McIntosh, H. V. (2006). Phenomenology of glider collisions in cellular automaton Rule 54 and associated logical gates. Chaos, Solitons & Fractals, 28(1), 100-111. DOI.

• Martínez, G. J., Adamatzky, A., & McIntosh, H. V. (2010). Localization dynamics in a binary two-dimensional cellular automaton: The Diffusion Rule. Journal of Cellular Automata, 5(4-5), 289-313. Publisher's issue contents; author-deposited preprint.

• Martínez, G. J., Adamatzky, A., Stephens, C. R., & Hoeflich, A. F. (2011). Cellular automaton supercolliders. International Journal of Modern Physics C, 22(4), 419-439. DOI.

• Meyer, D. A. (1996). From quantum cellular automata to quantum lattice gases. Journal of Statistical Physics, 85, 551-574. DOI.

• Morita, K. (2016). An 8-state simple reversible triangular cellular automaton that exhibits complex behavior. In M. Cook & T. Neary (Eds.), Cellular Automata and Discrete Complex Systems, Lecture Notes in Computer Science, 9664, 170-184. Springer. DOI.

• Nagel, K., & Schreckenberg, M. (1992). A cellular automaton model for freeway traffic. Journal de Physique I, 2(12), 2221-2229. Full text.

• Riedel, J., & Zenil, H. (2018). Cross-boundary behavioural reprogrammability reveals evidence of pervasive universality. International Journal of Unconventional Computing, 13(4-5), 309-357. Publisher's record.

• Sutner, K. (2013). Computational equivalence and classical recursion theory. In H. Zenil (Ed.), Irreducibility and Computational Equivalence: 10 Years After Wolfram's A New Kind of Science (pp. 297-307). Springer. DOI.

• 't Hooft, G. (2016). The Cellular Automaton Interpretation of Quantum Mechanics. Springer. DOI.

• Toffoli, T., & Margolus, N. (1987). Cellular Automata Machines: A New Environment for Modeling. MIT Press. Publisher's record.

• Turing, A. M. (1952). The chemical basis of morphogenesis. Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences, 237, 37-72. DOI.

• Ulam, S. (1962). On some mathematical problems connected with patterns of growth in figures. In R. Bellman (Ed.), Mathematical Problems in the Biological Sciences, Proceedings of Symposia in Applied Mathematics, 14, 215-224. American Mathematical Society. DOI.

• von Neumann, J. (1966). Theory of Self-Reproducing Automata. Edited and completed by A. W. Burks. University of Illinois Press.

• White, R., & Engelen, G. (1993). Cellular automata and fractal urban form: A cellular modelling approach to the evolution of urban land-use patterns. Environment and Planning A, 25(8), 1175-1199. DOI.

• Wolfram, S. (1983). Statistical mechanics of cellular automata. Reviews of Modern Physics, 55(3), 601-644. DOI.

• Wolfram, S. (1984). Universality and complexity in cellular automata. Physica D: Nonlinear Phenomena, 10(1-2), 1-35. Author's publication list.

• Wolfram, S. (1985). Twenty problems in the theory of cellular automata. Physica Scripta, T9, 170-183. DOI.

• Wolfram, S. (1986). Cryptography with cellular automata. In H. C. Williams (Ed.), Advances in Cryptology: CRYPTO '85 Proceedings, Lecture Notes in Computer Science, 218, 429-432. Springer. Author's publication list.

• Wolfram, S. (1994). Cellular Automata and Complexity: Collected Papers. Addison-Wesley. Author's full-text collection.

• Wolfram, S. (2002). A New Kind of Science. Wolfram Media. Online edition.

• Wuensche, A. (1999). Classifying cellular automata automatically: Finding gliders, filtering, and relating space-time patterns, attractor basins, and the Z parameter. Complexity, 4(3), 47-66. Full text.

• Wuensche, A. (2004). Self-reproduction by glider collisions: The beehive rule. In Artificial Life IX: Proceedings of the Ninth International Conference on the Simulation and Synthesis of Living Systems (pp. 286-291). MIT Press. Author's copy.

• Wuensche, A., & Adamatzky, A. (2006). On spiral glider-guns in hexagonal cellular automata: Activator-inhibitor paradigm. International Journal of Modern Physics C, 17(7), 1009-1026. DOI.

• Zenil, H. (2010). Compression-based investigation of the dynamical properties of cellular automata and other systems. Complex Systems, 19(1), 1-28. DOI.

• Zenil, H. (Ed.). (2012). A Computable Universe: Understanding and Exploring Nature as Computation. World Scientific.

• Zenil, H., Soler-Toscano, F., & Joosten, J. J. (2012). Empirical encounters with computational irreducibility and unpredictability. Minds and Machines, 22(3), 149-165. DOI.

• Zenil, H., & Villarreal-Zapata, E. (2013). Asymptotic behavior and ratios of complexity in cellular automata. International Journal of Bifurcation and Chaos, 23(9), 1350159. DOI.

• Zuse, K. (1970). Calculating Space. MIT Technical Translation AZT-70-164-GEMIT, Project MAC, Massachusetts Institute of Technology. English translation of Rechnender Raum (1969).

• Zwirn, H., & Delahaye, J.-P. (2013). Unpredictability and computational irreducibility. In H. Zenil (Ed.), Irreducibility and Computational Equivalence: 10 Years After Wolfram's A New Kind of Science (pp. 273-295). Springer. DOI.

Sponsored by: Eugene M. Izhikevich, Editor-in-Chief of Scholarpedia, the peer-reviewed open-access encyclopedia

Reviewed by: Prof. Andy Adamatzky, Dept of Computer Science - UWE, Bristol - UK

Reviewed by: Dr. Stephen Wolfram, Wolfram Research, Inc., IL, USA

Accepted on: 2024-04-01 00:14:00 GMT