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 discrete space, usually a regular lattice or grid. 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, and the new state of a cell depends on its current state and the states of the cells in a prescribed neighborhood. The cellular-automaton formalism is computationally universal in the sense that some cellular automata are Turing universal and can emulate other universal models of computation. One of the most salient features of cellular automata is their inherent parallelism: many regions are updated at the same time. Their space-time diagrams also provide compact visual representations of qualitatively diverse behaviors arising from different rules and initial conditions. This makes them useful both as abstract computational models and as simplified models of spatially extended physical and natural phenomena.

Two-dimensional Cellular Automata and Neighborhoods

In 1969, Konrad Zuse published the German original Rechnender Raum, and in 1970 its English translation appeared as Calculating Space. In that work, Zuse suggested that the universe's physical laws might be discrete by nature and that the physical universe itself could be regarded as the result of a deterministic computation on a cellular automaton-like substrate. He explored the idea that the physical universe could be represented as a discrete grid or lattice of cells, where each cell can be in one of a finite number of states and evolve according to deterministic rules based on the states of neighboring cells. Although Zuse's Calculating Space was not developed into a formal mathematical theory of cellular automata in the way that John von Neumann's work was, it remains an important early precursor to later digital-physics and cellular-automaton-based views of nature. A modern re-edition, written in modern typesetting by Adrian German and Hector Zenil with permission from Zuse's family, appeared in 2012 (Zuse, 1970; Zenil, 2012).

In the early 1950s, John von Neumann developed the first formal cellular-automaton framework in connection with the problem of self-reproduction, building on Stanisław Ulam's suggestion that discrete lattice-based systems could be used to study self-replicating processes. Nils Aall Barricelli also performed some of the earliest numerical experiments involving discrete evolving systems and artificial life. Much later, in 1984, Christopher Langton introduced a self-reproducing cellular automaton known as Langton's loops, a simpler construction than von Neumann's original universal constructor (Langton, 1984). A different type of neighborhood frequently used in two-dimensional cellular automata is the Moore neighborhood, named after Edward F. Moore. It consists of the eight cells surrounding a central cell: the four cardinal directions (north, south, east, west) and the four diagonal directions (northeast, northwest, southeast, southwest). The Moore neighborhood is commonly used in many two-dimensional cellular automata and simulations.

In 1970, John Conway introduced a two-state, two-dimensional cellular automaton with the Moore neighborhood, known as the Game of Life (GoL), which was popularized by Martin Gardner in a Scientific American article (Gardner, 1970). One of the most striking properties of GoL is that an extremely simple update rule can generate rich, persistent, and interacting structures. It was later shown to support universal computation. WireWorld is another well-known two-dimensional cellular automaton.

Elementary Cellular Automata

In the 1980s, Stephen Wolfram carried out an extensive systematic study of one-dimensional, two-state, nearest-neighbor cellular automata, which he called Elementary Cellular Automata (ECA) (Wolfram, 1983; Wolfram, 2002). These are among the simplest non-trivial cellular automata: each cell takes one of two values, usually 0 or 1, and the next state of a cell depends only on the state of the cell itself and its immediate left and right neighbors. Although the automata evolve on a one-dimensional lattice, their successive configurations are naturally displayed as two-dimensional space-time diagrams.

Wolfram's investigations of ECA and larger rule spaces highlighted the remarkable diversity of behavior that can arise even in very simple discrete dynamical systems. In particular, rules such as Rule 30 produce patterns that appear statistically random despite the simplicity and determinism of the underlying rule (Wolfram, 1983; Wolfram, 2002).

Rule-naming convention and higher dimensions

Wolfram introduced a simple enumeration scheme for ECA based on the binary representation of the rule table (Wolfram, 1983). Each ECA rule specifies an output for each of the eight possible local configurations of a cell and its immediate neighbors: 111, 110, 101, 100, 011, 010, 001, and 000. Since each output is binary, the list of outputs can be read as an 8-bit binary number. For example, the output string 00000010 corresponds to Rule 2. Because there are \(2^3 = 8\) possible neighborhood configurations and each can map to either 0 or 1, there are \(2^8 = 256\) elementary cellular automata in total.

If the number of states per cell or the size of the neighborhood is increased, the size of the corresponding rule space grows rapidly. In general, if a CA lives on a \(d\)-dimensional lattice, then its space-time evolution has dimension \(d+1\). Thus, ECA are one-dimensional automata with two-dimensional space-time evolutions, while the Game of Life is a two-dimensional automaton with a three-dimensional space-time evolution.

Researchers have extended the study of cellular automata to higher dimensions, larger alphabets, and more general neighborhoods. These extensions allow for the modeling of more complex phenomena and the exploration of a wider range of dynamical behaviors. Researchers such as Maurice Margenstern have also explored cellular automata in non-Euclidean geometries, especially hyperbolic spaces (Margenstern, 2007).

Types of boundary conditions

The choice of boundary conditions depends on the specific goals of a simulation or theoretical study. Different boundary conditions can lead to different behaviors and outcomes, and researchers often compare them in order to understand the robustness of a model and the influence of edge effects.

Periodic boundary conditions

Periodic boundary conditions, also called toroidal or wrap-around boundary conditions, identify opposite edges of the lattice. Cells at one edge of the grid are therefore treated as neighbors of cells at the opposite edge. This creates a seamless loop and is often used to reduce edge effects.

Fixed boundary conditions

Fixed boundary conditions, sometimes compared to Dirichlet boundary conditions, assign fixed values to cells at the boundary. These values do not change over time and are not updated from their neighbors.

Reflective boundary conditions

Reflective boundary conditions, sometimes compared to mirror or Neumann-type boundary conditions, treat the boundary as a reflection of nearby cells. They are used when a model is intended to capture symmetry or reflective constraints.

Absorbing boundary conditions

Absorbing boundary conditions treat the boundary as a sink. Information reaching the edge is lost or mapped to a quiescent value, such as 0. These conditions are useful when one wants activity to dissipate at the border.

Open boundary conditions

Open boundary conditions allow interaction with an external environment. Boundary cells may be influenced by inputs coming from outside the modeled region, or the edge may simply be left non-periodic and unconstrained.

Cellular automata as models of physics and their applications

Reversibility

Cellular automata are important tools for exploring the limits of computation, the emergence of complexity from simple rules, and the relationship between local interactions and global behavior. Edward Fredkin introduced the concept of reversible cellular automata and explored its implications for physics and computation (Fredkin, 1990). Together with Tommaso Toffoli and others, he helped establish reversible and partitioned cellular automata as important discrete models of physical processes.

A cellular automaton is reversible if there is exactly one past configuration (preimage) for every current configuration. If one thinks of a cellular automaton as a function mapping configurations to configurations, reversibility means that this function is bijective. In that case, the inverse dynamics is itself again a cellular automaton. This is related to the Curtis–Hedlund–Lyndon characterization of cellular automata as continuous, shift-commuting maps on symbolic configuration spaces. Configurations with no predecessor are called Garden of Eden configurations. Together with John Myhill, Edward F. Moore established the Garden of Eden theorem, which characterizes the relationship between such configurations and surjectivity.

For one-dimensional cellular automata there are algorithmic methods for deciding reversibility in important classes. In two or more dimensions, however, reversibility is undecidable: there is no general algorithm that, given an arbitrary rule, is guaranteed to determine correctly whether the automaton is reversible (Kari, 1990). Kari's proof is closely related to tiling arguments and the theory of Wang tiles.

Statistical mechanics, emergent phenomena and other applications

Fredkin and Wolfram were strong advocates of CA-based approaches to physics and simulation. Toffoli, Margolus, Morita, and others studied reversible and partitioned cellular automata as models of microscopic physical processes. Lattice-gas cellular automata were developed as discrete models of hydrodynamics, with a landmark example being the Frisch–Hasslacher–Pomeau model, which showed how local Boolean dynamics on a lattice can reproduce the Navier–Stokes equations at the macroscopic level (Frisch, Hasslacher, & Pomeau, 1986). Chopard and Droz surveyed many uses of cellular automata and related discrete models in physical systems (Chopard & Droz, 1998).

Probabilistic and excitable-media cellular automata have been used to study pattern formation, self-organization, and wave propagation (Griffeath, 1989). Connections between cellular automata and dynamical systems, including chaotic and complex behavior, have also been investigated (Umeo & Morita, 1997). Quantum cellular automata, as generalizations of classical cellular automata, have been studied as well (Isokawa, 1996). More recently, 't Hooft developed and elaborated a cellular-automaton interpretation of quantum mechanics in book form ('t Hooft, 2016).

Cellular automata have found applications in traffic modeling, with the Nagel–Schreckenberg model being a well-known example (Nagel & Schreckenberg, 1992). They have also been used more broadly as models of complex systems and artificial life (Bagnoli, 2005). Cellular automata have been applied to problems in statistical mechanics (Oliveira, 2005), and their algebraic and group-theoretic properties have been studied in detail, including questions related to reversibility and surjunctivity (Ceccherini-Silberstein & Coornaert, 2010). General dynamical, structural, and attractor-related aspects of cellular automata have also been studied extensively (Dennunzio, Formenti, & Kůrka, 2012; Goles, 2001). Cellular automata have been applied to urban dynamics and land-use modeling as well (Jolivet & Sanders, 2006), and they continue to serve as useful simplified models of natural and complex phenomena more broadly (Gómez Soto, 2009).

Cellular automata have also been used to generate procedural textures and patterns in computer graphics. They can create visually interesting and dynamic effects for video games, films, and digital art. CA have further been used in cryptography, including pseudorandom generation and stream-cipher-like constructions (Wolfram, 1986).

Cellular automata as models of computation

Computability and reachability

The study of cellular automata and universal computation has revealed deep connections between dynamical systems and theoretical computer science. Cellular automata provide a rich framework for exploring questions about computation, complexity, and the emergence of organized behavior from simple local rules.

A cellular automaton is said to be intrinsically universal if it can simulate the behavior of any other cellular automaton, and simply universal if it is capable of universal Turing computation. Significant contributions to cellular-automaton theory have been made in automaton dynamics, language recognition, decidability, and computational complexity (Culik II, Hurd, & Yu, 1990; Kutrib, 2016; Sutner, 2013). Reachability concerns whether one configuration can evolve into another through repeated application of a rule. Reversibility is closely related to reachability because reversible systems allow motion both forward and backward through configuration space. Reliable computation in the presence of noise has also been studied in depth (Gács, 1987).

Dynamical systems, logic and circuits

Efforts to analyze and visualize cellular automata have yielded insights into attractor basins, that is, sets of configurations that eventually evolve to the same long-term behavior (Wuensche, 1998).

Collision-based computation using particles, gliders, and their interactions has been studied in several cellular-automaton systems, including Rule 54 and cellular-automaton supercolliders (Martínez, Adamatzky, McIntosh, & Seck-Tuoh-Mora, 2006; Martínez, Adamatzky, Stephens, & Hoeflich, 2011). Theoretical aspects of cellular automata, including tilings, decidability, and computational complexity, continue to provide important insights into their capabilities and limitations (Durand, 2010).

Fuzzy cellular automata have been developed to handle uncertainty and imprecision, enabling the modeling and analysis of complex systems under graded rather than purely discrete truth values (Perfilieva & Bouchon-Meunier, 2009). More broadly, cellular automata remain important models in unconventional computing.

Wolfram's principles of Computational Irreducibility and Equivalence

Cellular automata are often used to explore philosophical questions about emergence and reductionism. They show how complex global behavior can arise from simple local rules, and they therefore challenge the idea that understanding isolated components is always sufficient to understand the behavior of the whole system.

Wolfram argued that many questions about cellular-automaton evolution cannot, in general, be shortcut without effectively following the computation in detail (Wolfram, 1985; Wolfram, 2002). He later called this idea the Principle of Computational Irreducibility (Wolfram, 2002). The idea has since been examined from several perspectives. For example, Israeli and Goldenfeld showed that coarse-graining can sometimes yield predictive reductions for classes of cellular automata (Israeli & Goldenfeld, 2006). Related questions have also been discussed in terms of computability, recursion theory, language recognition, and formal unpredictability (Sutner, 2012; Sutner, 2013; Zwirn & Delahaye, 2012). Experimental and empirical approaches to irreducibility have also been proposed (Zenil, Soler-Toscano, & Joosten, 2012).

Rule 110, an elementary cellular automaton, was conjectured by Wolfram to be universal and later proved to support universal computation by Matthew Cook (Cook, 2004; Wolfram, 2002). The existence of such a simple universal rule contributed to Wolfram's Principle of Computational Equivalence (PCE), according to which systems that are not obviously simple tend to exhibit computations of equivalent sophistication (Wolfram, 2002). Later work on reprogrammability provided empirical evidence that many non-trivial ECA rules can emulate rules with qualitatively different behavior under suitable compilers or rescalings (Riedel & Zenil, 2018).

Classification of Cellular Automata

Stephen Wolfram introduced a well-known behavioral classification of cellular automata based on their long-term space-time behavior. This classification has been influential in understanding the range of dynamical behaviors that cellular automata can exhibit, from simple and predictable to chaotic and complex.

Wolfram observed different kinds of behavior when cellular automata were evolved from random initial conditions and proposed the following heuristic classes:

• Class 1: Nearly all initial patterns evolve quickly into a stable, homogeneous state. Any randomness in the initial pattern disappears.
• Class 2: Nearly all initial patterns evolve quickly into stable or oscillating structures. Some randomness may persist locally, but local changes tend to remain localized.
• Class 3: Nearly all initial patterns evolve in a pseudo-random or chaotic manner. Local changes tend to spread indefinitely.
• Class 4: Initial patterns evolve into structures that interact in complex ways, often involving localized persistent objects.

Rules such as ECA Rule 110, like the Game of Life, are commonly associated with Class 4 behavior. Rules such as ECA Rule 30 are commonly associated with Class 3 behavior. Attempts to formalize or refine Wolfram's classification have led to a variety of approaches based on attractor structure, information-theoretic quantities, mean-field methods, power spectra, lossless compression, and algorithmic complexity (Li & Packard, 1990; Wuensche, 1998; Zenil, 2010; Zenil, 2013). These approaches can broadly be divided into rule-based and post-evolution-based methods. Rule-based approaches inspect the generating rule itself; a well-known example is Langton's lambda parameter, which measures the density of non-quiescent outputs in a rule table.

Limitations

No single complete automatic classification of cellular automata is known in general, and many non-trivial dynamical properties of cellular automata are undecidable (Culik II, Hurd, & Yu, 1990; Kari, 2005). Post-evolution approaches also depend on the choice of initial conditions and on the observer's descriptive framework. Even so, they are often more flexible than purely rule-based methods because they can incorporate how a rule behaves across a distribution of inputs rather than only how the static rule table is written.

Mean field theory (MFT)

Mean field theory is a mathematical approach used to approximate the behavior of complex systems by assuming that each component interacts with an average or effective field representing the influence of the rest of the system. In the context of cellular automata, mean field theory has been used to derive analytical approximations to quantities such as average state densities and coarse dynamical tendencies, especially for large systems where direct analysis is difficult.

Entropy and lossless compression

Measures such as entropy and practical lossless compression primarily capture statistical regularities. Algorithmic-information approaches aim to capture broader forms of regularity, although in practice they can only be approximated. Riedel and Zenil argued that many non-trivial rules can emulate rules from other behavioral classes, suggesting that behavioral classification is not always absolute but can depend on the availability of suitable compilers or transformations (Riedel & Zenil, 2018).

Sensitivity and perturbation analysis

When studying sensitivity to initial conditions, one must define a distance between initial configurations. One convenient choice is Gray-code ordering, because consecutive strings differ in only one bit and therefore represent minimal perturbations of the initial condition.

Several Lyapunov-like, damage-spreading, and perturbation-growth measures have been adapted to cellular automata. These quantify how differences in nearby initial configurations grow or shrink under the dynamics, and they have been used to help distinguish ordered, chaotic, and complex regimes.

Subclasses of Cellular Automata

Totalistic

A totalistic cellular automaton is a cellular automaton in which the next state of each cell depends only on the sum, or total, of the values in its neighborhood, sometimes including the cell itself. In other words, the transition rule depends on the total value of the neighborhood rather than on the precise arrangement of those values.

In a one-dimensional binary totalistic cellular automaton, the next state of a cell is determined by the sum of the values of the three cells in its neighborhood. Since the sum can take values from 0 to 3, the rule can be specified by assigning an output to each of these four sums. If the next state depends on the total of the neighbors together with the cell's own current state, the automaton is more precisely called outer totalistic. Conway's Game of Life is an example of an outer-totalistic cellular automaton, and two-dimensional outer-totalistic automata with the Moore neighborhood are often called life-like cellular automata.

Stochastic Cellular Automata

Stochastic cellular automata incorporate an element of randomness into their update rules. The next state of a cell is determined probabilistically, conditioned on the current states of the cells in its neighborhood.

Continuous-valued and reaction-diffusion variants

Some extensions of the cellular-automaton idea allow continuous state values or more general spatial domains. These are not standard cellular automata in the strict classical sense, but they are closely related modeling frameworks. Reaction-diffusion systems, for example, are usually formulated as continuous differential equations rather than as cellular automata, yet they can often be approximated or mimicked by suitable discrete lattice models. Alan Turing's work on morphogenesis is a classic example of a reaction-diffusion approach to pattern formation. The Belousov–Zhabotinsky reaction is another well-known source of inspiration for excitable-media and reaction-diffusion cellular-automaton models.

Non-uniform Cellular Automata

Non-uniform cellular automata are cellular automata in which different cells may follow different local update rules. This allows the modeling of heterogeneous systems with varying local behavior.

Lattice Gas Automata

Lattice-gas automata are cellular-automaton-like systems used to simulate fluids and gases. They model particles moving and colliding on a lattice under local conservation laws.

Non-square lattice/grid

Cellular automata do not have to be defined on square lattices. They can also be defined on triangular, hexagonal, hyperbolic, spherical, graph-based, and other non-regular or non-Euclidean structures. Margenstern, for example, developed cellular automata in hyperbolic spaces (Margenstern, 2007). In graph-based cellular automata, the neighborhood of a cell is determined by the edges of the graph rather than by geometric adjacency on a regular lattice.

References

• Bagnoli, F. (2005). Complex systems and artificial life. In A. Adamatzky (Ed.), Collision-Based Computing (pp. 11-53). Springer.

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

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

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

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

• 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.

• Durand, B. (2010). Decision problems for tile sets. Journal of Computer and System Sciences, 76(8), 707-716.

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

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

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

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

• Gómez Soto, J. M. (2009). Cellular automata and complex systems. International Journal of Modern Physics C, 20(3), 367-376.

• Goles, E. (2001). The structure of binary cellular automata. Journal of Statistical Physics, 102(3-4), 751-764.

• Griffeath, D. (1989). A cellular automaton model for excitable media. Journal of Statistical Physics, 54(3-4), 675-695.

• Isokawa, T. (1996). Generalized quantum cellular automata. Physica D: Nonlinear Phenomena, 97(1-3), 81-99.

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

• Jolivet, T., & Sanders, W. H. (2006). Urban cellular automata: Generating transition rules using microscale behavior. Computers, Environment and Urban Systems, 30(6), 861-887.

• 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.

• Kutrib, M. (2016). Cellular automata. In J. van Leeuwen (Ed.), Encyclopedia of Algorithms (pp. 349-355). Springer.

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

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

• Margenstern, M. (2007). Cellular Automata in Hyperbolic Spaces, Volume 1. Old City Publishing.

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

• 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.

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

• Oliveira, P. P. B. de. (2005). A class of cellular automata applied to problems in statistical mechanics. Physica A: Statistical Mechanics and Its Applications, 350(2-4), 460-468.

• Perfilieva, I., & Bouchon-Meunier, B. (2009). Fuzzy cellular automata: A study of their ability to compute fuzzy functions. Fuzzy Sets and Systems, 160(22), 3230-3247.

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

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

• Sutner, K. (2013). Cellular automata and language recognition. Theoretical Computer Science, 488, 2-23.

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

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

• Umeo, H., & Morita, K. (1997). Dynamics and chaos of cellular automata. Physical Review E, 56(1), 1346-1357.

• von Neumann, J. (1951). The general and logical theory of automata. In L. A. Jeffress (Ed.), Cerebral Mechanisms in Behavior: The Hixon Symposium (pp. 1-31). John Wiley & Sons.

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

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

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

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

• Wuensche, A. (1998). Classifying elementary cellular automata: Discovering new attractor basins. Complex Systems, 10(4), 299-325.

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

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

• Zenil, H. (2013). Asymptotic behaviour and ratios of complexity in cellular automata. International Journal of Bifurcation and Chaos, 23(9), 1350159.

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

• Zuse, K. (1970). Calculating Space. MIT Technical Translation AZT-70-164-GEMIT, Project MAC, Massachusetts Institute of Technology, Cambridge, MA.

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

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