Cellular automata

A cellular automaton is a deterministic rewriting dynamical system that evolves in discrete time and discrete space, usually a grid. It consists of a local grid of cells that are synchronously updated across the grid according to a global time scale and a global recursive rule governing the evolution of the state of each cell as a function of the state of neighboring cells. While the model of cellular automata is of the same computational power as other Turing universal models and, therefore, fundamentally equivalent as they can emulate each other, one of the most salient features of cellular automata is their parallelism that allows multiple regions to get updated at the same time and the qualitative diversity of their space-time evolutions when exploring different rules and different initial conditions. Their characteristic patterns appear faster than in other computing models. They are shown visually compactly due to their updating synchronous nature, making them suitable to be rapidly studied quantitatively and qualitatively after only a few computation steps and compared to highly apparent simultaneously-updated physical and natural phenomena.

Contents 1 Two-dimensional Cellular Automata and Neighborhoods 2 Elementary Cellular Automata 3 Rule-naming convention and higher dimensions 4 Types of boundary conditions 5 Cellular automata as models of physics and its applications 6 Cellular Automata as models of computation 7 Wolfram's principles of Computational Irreducibility and Equivalence 8 Classification of Cellular Automata 9 Subclasses of Cellular Automata

[edit] Two-dimensional Cellular Automata and Neighborhoods

In 1969, Konrad Zuse published his manuscript 'Calculating Space' where he suggested that the universe's physical laws could be discrete by nature and that the entire universe is the output of a deterministic computation on a single cellular automaton. Zuse 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. The state of each cell would evolve according to deterministic rules based on the states of its neighboring cells. While Zuse's calculating space was not developed into a formal mathematical model like John von Neumann's cellular automata, it represents an early mention and precursor in anticipation of a profound question in the field. Calculating Space by Zuse was entirely rewritten by Zenil and German in modern typesetting with permission from his family, fixing some notation issues before publication (Zenil, 2012).

In fluid dynamics and biological systems, two-dimensional cellular automata were studied in the early 1950s by people such as Stanislaw Ulam, John von Neumann, and Nils Aall Barricelli. Ulam and von Neumann created a method for calculating liquid motion in the late 1950s. The driving concept of the method was to consider a liquid as a group of discrete units and calculate the motion of each based on its neighbors' behavior. Ulam suggested using a discrete system for creating a reductionist model of self-replication. John von Neumann considered these cellular automata models in its quest to investigate and discover a universal constructor, a computational model that could describe itself and self-reproduce. Much later, in 1986, Christopher Langton found a self-reproducing cellular automaton named Langton's ant found in a small rule space (fewer states/shorter rule) than that constructed by von Neumann. Barricelli performed many of the earliest numerical experiments of cellular automata as a framework for artificial life as a precursor of evolutionary algorithms. A different type of neighborhood considered by von Neumann in two-dimensional cellular automata is the neighborhood named after Edward F. Moore, an early pioneer of cellular automata theory (Moore). It consists of the eight cells surrounding a central cell, including the four cardinal directions (north, south, east, west) and the four diagonal directions (northeast, northwest, southeast, southwest). The Moore neighborhood is commonly used in various cellular automata models and simulations.

In the 1970s, John Conway introduced a two-state, two-dimensional cellular automaton with Moore's neighborhood, known as the 'Game of Life' (GoL), as popularised by Martin Gardner in a Scientific American article. One of the most striking properties of GoL is not only that it appears to capture some of the most basic processes of life (birth, reproduction, and death) in an extremely simple model but the model displays the kind of living system's rich behavior. GoL was later proven to be Turing universal. WireWorld is another common two-dimensional cellular automaton.

[edit] Elementary Cellular Automata

In the mid-1980s, a comprehensive search of cellular automata models was performed by Stephen Wolfram, who contributed significantly to the expansion and professionalization of the field. Wolfram systematically studied and introduced a simplified model of cellular automata, particularly the simplest non-trivial consisting of one-dimensional-space, two-state automata that produce two-dimensional space-time evolutions (Wolfram, 1983). Those living in one-dimensional space and considering only the state of the closest two-cell neighbors were named Elementary Cellular Automata (Wolfram, 2002). Elementary cellular automata have two possible values for each cell (0 or 1), and rules that depend only on nearest neighbor values. Wolfram performed an exhaustive and systematic study of ECA and other rewriting systems in increasingly larger rule spaces, as published in his book A New Kind of Science (2002). Among his discoveries is that even in the simplest CA models, some rules could generate high-quality statistical randomness even for the simplest initial conditions. This came as a surprise because even when some simple dynamical systems were known to be able to produce chaotic behavior, such as in the so-called Rule 30 (where 30 comes from the rule representation in binary converted to decimal), such chaotic behavior would be, however, the result of continuous-time or continuous-space supporting such random-looking behavior. In cellular automata, however, rules and initial conditions are simple, such as in other discrete or continuous dynamical systems, and they also run on discrete space and time.

[edit] Rule-naming convention and higher dimensions

Wolfram was the first to explore CAs systematically and conceived a simple enumeration scheme based on the rule representation (Wolfram, 1983). Each elementary cellular automata (ECA) rule can be represented by a row of all 3-tuple (the central cell and its closest neighbors), of which there are 8 cases, followed by a row of the rule assignation to either a white or a black cell. Given that the ECA is a 2-state rule space, can be read as a binary number e.g., 00000010, which in decimal is, e.g., rule 3. There are 2×2×2=2^3=8 possible binary states for the three cells neighboring a given cell. All possible mappings give a total number of \(2^8=256\) rules. Increasing the state (color) number or the number of neighbors to each side in the description of each rile, the rule space size increases exponentially with ever-increasing spaces, including the smaller ones. Space-time evolutions are of \(d+1\) dimensions where d is the dimension of the CA \(+\) time. For example, ECA that are 2-dimensional evolves in three dimensions. CAs such as the Game of Life that are 3-dimensional produce space-time evolutions in 4 dimensions.

Researchers have extended the study of CA to higher dimensions (e.g., three-dimensional CA) and larger rule spaces (e.g., CA with more than two states per cell). These extensions allow for the modeling of more complex phenomena and the exploration of a wider range of dynamical behavior. Researchers like Juarez Martinez and Margenstern have also explored CA in non-Euclidean geometries, such as hyperbolic and spherical spaces. These studies have led to new insights into the behavior of CA in curved geometries and the potential applications of CA in modeling natural phenomena.

[edit] Types of boundary conditions

The choice of boundary conditions depends on the specific goals and requirements of the simulation or study. Different boundary conditions can lead to different behaviors and outcomes, and researchers often explore the effects of different boundary conditions to understand the robustness and sensitivity of the CA to boundary effects.

Periodic Boundary Conditions

Periodic boundary conditions, also known as toroidal or wrap-around boundary conditions, treat the grid or lattice as if it were a torus (a doughnut-shaped surface). In this case, cells at one edge of the grid are considered neighbors of cells at the opposite edge. This creates a seamless loop, allowing information to wrap around the grid without any discontinuities. Periodic boundary conditions are often used in simulations where the goal is to minimize edge effects and study the behavior of the CA in an infinite or unbounded space.

Fixed Boundary Conditions

Fixed boundary conditions, also known as Dirichlet boundary conditions, specify fixed values for cells at the boundaries of the grid. These fixed values do not change over time and are not influenced by the states of neighboring cells. Fixed boundary conditions are used when the behavior of cells at the boundaries is known or predetermined, or when the boundaries represent physical barriers or constraints.

Reflective Boundary Conditions

Reflective boundary conditions, also known as Neumann or mirror boundary conditions, treat the boundaries as mirrors that reflect the states of neighboring cells. In this case, cells at the edges have neighbors that are reflections of cells on the opposite side of the boundary. Reflective boundary conditions are used when the boundaries represent reflective or symmetric surfaces, or when the goal is to simulate a system with symmetry or conservation properties.

Absorbing Boundary Conditions

Absorbing boundary conditions treat the boundaries as sinks that absorb information or states from neighboring cells. In this case, cells at the boundaries may have fixed values (e.g., always zero) or may not influence the states of neighboring cells. Absorbing boundary conditions are used when the boundaries represent absorbing surfaces or when the goal is to simulate the dissipation or loss of information at the edges of the system.

Open Boundary Conditions

Open boundary conditions allow information to flow freely into or out of the grid. In this case, cells at the boundaries may be influenced by external inputs or may have states determined by external conditions. Open boundary conditions are used when the goal is to simulate interactions between the CA and its environment or when the boundaries represent open or dynamic systems.

[edit] Cellular automata as models of physics and its applications

Reversibility

Cellular automata are a powerful tool for exploring the limits of computation, the emergence of complexity from simple rules, and the interplay between local interactions and global behavior. Edward Fredkin introduced the concept of reversible cellular automata and explored their implications for computation and physics. With Tommaso Toffoli, they conducted research on reversible cellular automata. They explored the connections between cellular automata and the laws of physics. Reversibility is a key property of certain cellular automata that allows for the time-reversal of their dynamics. A cellular automaton is reversible if, for every configuration, there exists a unique predecessor configuration that leads to it. Reversible cellular automata are important for the study of conservation laws and the simulation of physical systems that obey such laws.

A cellular automaton is reversible if there is exactly one past configuration (preimage) for every current configuration of the cellular automaton. If one thinks of a cellular automaton as a function mapping configurations to configurations, reversibility implies that this function is bijective. If a cellular automaton is reversible, its time-reversed behavior can also be described as a cellular automaton; this is a consequence of the Curtis–Hedlund–Lyndon theorem, a topological characterization of cellular automata. The configurations without preimages are called 'Garden of Eden' patterns for cellular automata in which not every configuration has a preimage. With John Myhill, Moore proved the Garden of Eden theorem characterizing the cellular automaton rules that have patterns with no predecessor.

For one-dimensional cellular automata, there are known algorithms for deciding whether a rule is reversible or irreversible. However, for cellular automata of two or more dimensions, reversibility is undecidable; that is, no algorithm takes as input an automaton rule and is guaranteed to determine correctly whether the automaton is reversible. The proof by Jarkko Kari is related to the tiling problem by Wang tiles.

Reversible cellular automata are often used to simulate such physical phenomena as gas and fluid dynamics since they obey the laws of thermodynamics (Frisch, Hasslacher, and Pomeau, 1986). Such cellular automata have rules specially constructed to be reversible. Such systems have been studied by Tommaso Toffoli, Norman Margolus, and others. Several techniques can be used to construct reversible cellular automata with known inverses explicitly.

Statistical mechanics, emergent phenomena and other applications

Fredkin and Wolfram were strong proponents of CA-based physics for modeling and simulation purposes. Norman Margolus and Kenichi Morita investigated reversible cellular automata as models of irreversible physical phenomena and entropy. Margolus introduced the Margolus neighborhood used in certain types of cellular automata. Probabilistic cellular automata have been applied to the study of emergent phenomena in complex systems, including pattern formation, self-organization, and growth processes (Griffeath, 1989). Connections between cellular automata and dynamic systems, such as chaos, have been established, exploring various classes of automata and their behavior (Umeo & Morita, 1997). Asynchronous cellular automata, which involve non-simultaneous updates of cells, have been extensively studied (Imai et al., 1999). Quantum cellular automata, a generalization of classical cellular automata, have also been investigated (Isokawa, 1996). 't Hooft (2016) developed and elaborated upon the idea of rebuilding quantum mechanics using cellular automata in a book-length publication.

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 to model social dynamics, epidemics, and other complex phenomena (Bagnoli, 2005). Lattice gases with probabilistic cellular automata have been studied in the context of statistical mechanics (Oliveira, 2005). The study of cellular automata in the context of reversibility, conservation laws, and universality has been explored (Kari & Guillon, 1998). Chopard (2002) investigated the use of lattice Boltzmann methods and cellular automata for simulating fluid dynamics and physical systems.

Theoretical aspects of cellular automata, including their dynamics, reversibility, and complexity, have been research subjects (Alonso-Sanz, 2007). Cellular automata have been applied to the study of urban dynamics, including urban growth and land-use change (Jolivet & Sanders, 2006). The behavior, attractors, and ergodic properties of cellular automata have been analyzed (Formenti, 2010; Goles, 2001). Furthermore, cellular automata have been employed in modeling natural phenomena, such as ecological systems and the spread of diseases (Gómez Soto, 2009).

Cellular Automata have been used to generate procedural textures and patterns in computer graphics. They can create visually interesting and dynamic effects for use in video games, movies, and digital art. CA have also been used in the design of cryptographic algorithms, including pseudorandom number generators and stream ciphers (Wolfgang, 1995).

[edit] Cellular Automata as models of computation

Computability and Reachability

Overall, the connections between cellular automata and Turing universal computability have deepened our understanding of the fundamental principles of computation and the behavior of complex systems. The study of cellular automata and Turing universal computability has revealed deep connections between the fields of dynamical systems and theoretical computer science. Cellular automata provide a rich framework for exploring fundamental questions about the nature of computation, complexity, and the emergence of organized behavior from simple rules.

A cellular automaton is said to be intrinsically universal if it can simulate the behavior of any other cellular automaton, or simply universal if capable of universal Turing computation. Significant contributions have been made in various areas of cellular automata theory, including automata dynamics, language recognition, reachability, decidability, and computational complexity (Kutrib, 2016; Culik II & Yu, 2003; Sutner, 2013). Reachability is a fundamental concept in understanding cellular automata dynamics, referring to the ability to transition between configurations through rule applications (Margolus & Toffoli, 1987). Reversibility, closely related to reachability, enables transitions in both forward and backward directions. Some research has also focused on exploring cellular automata's computational power, noise sensitivity, and probabilistic behavior (Gacs, 1987).

Dynamical systems, logic and circuits

Efforts have been made to analyze and visualize cellular automata, yielding insights into the structure and properties of attractor basins, which are sets of configurations evolving to the same attractor (Wuensche, 1998).

Unconventional computation and problem-solving using cellular automata have led to the investigation of collision-based computation on rings, utilizing particle interactions and collisions for computation (Martinez & Adamatzky, 2005). Theoretical aspects of cellular automata theory, including tilings, decidability, and computational complexity, provide insights into their fundamental properties and limitations (Durand, 2010).

Fuzzy cellular automata have been developed to handle uncertainty and imprecision, enabling the modeling and analysis of complex systems (Perfilieva & Bouchon-Meunier, 2009). Cellular automata also find applications in unconventional computing, serving as tools for modeling complex systems and exploring novel computational paradigms (Stepney, 2003).

[edit] Wolfram's principles of Computational Irreducibility and Equivalence

Cellular automata are often used to explore philosophical questions about emergence and reductionism. CA demonstrate how complex global behavior can emerge from simple local rules, challenging the idea that understanding individual components is sufficient to understand the whole system. This has implications for debates about the nature of reality and the relationship between parts and wholes.

In the late 1990s, Wolfram suspected that most questions regarding long and even short-range reachability involving CA evolutions were, in a sense, unsolvable without having to simulate the CA (almost) step by step (Wolfram 1983, Wolfram 1985, Wolfram 2002). He called this concept the Principle of Computational Irreducibility (Wolfram, 2002). The concept of irreducibility was explored by various groups, with some researchers finding some ways to make short-range predictions of apparent random cellular automata by finding certain patterns after coarse-graining (Israeli and Goldenfeld, 2006). Later, reducibility was connected to computability, reachability, and language recognition in more technical detail (Sutner, 2012; Sutner 2013) and other attempts to formalize it (Zwrin and Delahaye, 2012) and even explored and approached experimentally with results that strengthened Wolfram's intuition (Zenil, Soler-Toscano, and Joosten, 2012).

Also, in the early 2000s, Wolfram and Cook showed that another ECA Rule, Rule 110, was capable of Turing universality (Wolfram, 2002). The rule is so minimalistic yet computationally powerful that it led Wolfram to postulate a Principle of Computational Equivalence (PCE), establishing that rules capable of non-trivial behavior were equally powerful and able of Turing universality. PCE was later explored (Riedel and Zenil, 2018), showing that most non-trivial ECA rules could be reprogrammed to behave as other rules displaying very different qualitative behavior with the appropriate compiler under rescaling factors (effectively a generalization of the coarse-graining techniques) hence providing further evidence in favor of Wolfram's PCE contributing to the understanding of computation universality in cellular automata by providing a method for identifying candidate rules that may exhibit universal behavior based on their algorithmic complexity (Riedel and Zenil, 2018).

[edit] Classification of Cellular Automata

The classification of cellular automata based on their behavior, as introduced by Stephen Wolfram, has provided insights into the types of dynamics that cellular automata can exhibit, from simple and predictable to chaotic and complex.

Wolfram observed various qualitatively different behaviors in their space-time evolutions starting with random initial conditions. The discovery of the various qualitative behaviors displayed by ECA led Wolfram to propose a behavioral heuristic classification:

• 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 in the initial pattern may filter out, but some remain. Local changes to the initial pattern tend to remain local.
• Class 3: Nearly all initial patterns evolve in a pseudo-random or chaotic manner. The surrounding noise quickly destroys any stable structures that appear. Local changes to the initial pattern tend to spread indefinitely.
• Class 4: Nearly all initial patterns evolve into structures that interact in complex and interesting ways, with the formation of local structures that are able to survive for long periods of time.

Rules such as ECA rule 110, like the Game of Life, exhibit Class 4 behavior. Rules like ECA rule 30 that are random-looking belong to Class 3. Attempts to formalize the classification or develop alternatives have led to different approaches and proposals, including A. Wuensche, W. Li, and N.H. Packard, J. Baetens, H. Zenil, and others, based on other order parameters such as information (communication) theoretic (statistical entropy), power spectral, topological, surface, lossless compression (such as LZW), lattices, Lyapunov exponents, algorithmic complexity, mean-field, and morphological diversity classifications. They can themselves be categorized into rule-based or post-evolution-based. Rule-based approaches focus on an examination of the generating rules. This is the case of, for example, Langton's lambda parameter (the rule density of non-zero values).

Limitations

These approaches, however, are very limited because of undecidability results (Culik et al.) Post-evolution approaches are observer-dependent by the same undecidability arguments. Still, they are better placed to adapt under a Bayesian approach to behavior that updates its class membership (as compared to those classifications based on only inspecting the generating rules), such as entropy, Lyapunov's exponent, lossless compression, or algorithmic-complexity-based. Post-evolution approaches also allow a qualitative study of the sensitivity of a rule to different initial conditions.

For example, ECA rule 22 is bi-stable, with one behavior belonging to Class 2 as it produces a Sierpinsky fractal-like pattern and another behavior to which it converges in the limit as a function of initial input length it produces a random-looking output similar to that of ECA rule 30 (because the longer the string, the fewer chances to have the symmetry required to produce the fractal-like behavior). This kind of analysis is impossible with rule-based approaches such as Langton's lambda or state diagrams only inspecting the static rule.

Mean field theory (MFT)

MFT is a mathematical approach used to approximate the behavior of complex systems by assuming that each component of the system (e.g., each cell in a cellular automaton) interacts with an average or mean field that represents the influence of all other components. In the context of cellular automata (CA), mean field theory has been used to provide analytical approximations of the behavior of CA, especially for large systems where direct simulation may be computationally expensive.

In mean field theory for cellular automata, the state of each cell is assumed to be influenced by an average or mean state that represents the collective behavior of the entire system. This approximation allows researchers to derive equations that describe the macroscopic behavior of the CA, such as the average density of cells in a particular state or the overall dynamics of the system.

Entropy and lossless compression

Measures, such as entropy or lossless compression with popular compression algorithms, are limited to statistical (i)regularities. Only measures able to cope with undecidable problems such as those universal, like algorithmic complexity and algorithmic probability introduced by J. Riedel and Zenil are equipped, in principle, to deal with the range of rich and possible behavior displayed by a universal model such as CA. Riedel and Zenil also showed that classifications are not fundamental because, for every (non-trivial) rule, there is a compiler with which the rule can be reprogrammed to emulate rules from any other behavioral class. However, they also showed that a new classification could be recovered by looking at how difficult it is for a rule-compiler tuple to be found in order to emulate a wider range of rules both quantitatively and qualitatively different. The invariant is, therefore, the combination of the most likely behavior and the algorithmic probability of finding a short compiler to make the original rule emulate other rules.

Sensitivity and perturbation analysis

When considering the sensitivity to initial conditions, one has to define a distance between initial conditions, and the most appropriate is to use Gray's code that guarantees that only one digit changes from one to another string hence only introducing the smallest possible change in the initial condition to study its effect in the output evolution of the CA.

Lyapunov exponents are a measure of the sensitivity of a dynamical system to small perturbations in its initial conditions. Specifically, they quantify the rate at which nearby trajectories in the system's state space diverge or converge over time. Positive Lyapunov exponents indicate sensitive dependence on initial conditions (chaotic behavior), while negative exponents indicate convergence to a stable state or attractor. In the context of cellular automata (CA), Lyapunov exponents have been used to characterize the dynamical behavior of CA and to distinguish between ordered, chaotic, and complex behavior.

The concept of Lyapunov exponents for cellular automata was introduced and studied by researchers such as Pierre Grassberger, Tommaso Toffoli, and Norman H. Packard. The computation of Lyapunov exponents for CA involves analyzing the response of the CA to small perturbations in the initial configuration and quantifying the rate of divergence of nearby configurations over time.

Grassberger, for example, studied the Lyapunov exponents of one-dimensional CA and showed that they can be used to distinguish between different classes of CA behavior. He also demonstrated that CA with positive Lyapunov exponents exhibit chaotic behavior, while those with negative exponents exhibit more ordered behavior.

[edit] Subclasses of Cellular Automata

Totalistic

A totalistic cellular automaton is a type of cellular automaton in which the next state of each cell depends only on the sum (or total) of the states of the cells in its neighborhood, including its own state. In other words, the transition rule for a totalistic cellular automaton is determined by the total value of the states of neighboring cells, rather than by the specific configuration of those states.

The state of each cell in a totalistic cellular automaton is represented by a number (usually an integer value drawn from a finite set), and the value of a cell at time t depends only on the sum of the values of the cells in its neighborhood (possibly including the cell itself) at time \(t - 1\). If the state of the cell at time t depends on its own state and the total of its neighbors at time \(t − 1\), then the cellular automaton is correctly called outer totalistic. Conway's GoL is an example of an outer totalistic cellular automaton with cell values 0 and 1; outer totalistic cellular automata with the same Moore neighborhood structure as Life are sometimes called life-like cellular automata.

In a one-dimensional binary totalistic cellular automaton, the next state of a cell is determined by the sum of the states of the three cells in its neighborhood. Since the sum can take on values from 0 to 3, the transition rule can be defined by specifying the next state for each of these four possible sums. For example, a rule might specify that a cell will be in state 1 in the next time step if the sum of its neighborhood is 1 or 2, and in state 0 otherwise.

Stochastic Cellular Automata

Stochastic CA are CA that incorporate an element of randomness into their transition rules. The next state of a cell is determined probabilistically based on the states of its neighbors.

Continuous spatial automata

Continuous spatial automata have a continuum of locations. The state of a location is a finite number of real numbers. Time is also continuous, and the state evolves according to differential equations. One important example is reaction-diffusion textures, differential equations proposed by Alan Turing in the context of his morphogenesis to explain how chemical reactions could create the stripes on zebras and spots on leopards. The Belousov–Zhabotinsky reaction is a spatiotemporal chemical oscillator that can be simulated using a cellular automaton.

Non-Uniform Cellular Automata

Non-uniform CA are CA in which different cells can have different transition rules. This allows for the modeling of heterogeneous systems with varying local behavior.

Lattice Gas Automata

Lattice gas automata are CA used to simulate fluid dynamics. They model the movement of particles on a lattice and their collisions.

Cellular Automata in Non-Euclidean Geometries: CA can also be defined on non-Euclidean geometries, such as hyperbolic or spherical spaces. These CA provide insights into the behavior of automata in curved geometries.

Non-square lattice/grid

Lattices on which a CA runs do not have to be square. Maurice Margenstern, for example, has introduced CA on hyperbolic planes. : In some cellular automata, neighborhoods may be defined in an arbitrary or custom manner. This allows for the modeling of specific interactions or topologies that do not conform to the standard neighborhood shapes. In cellular automata defined on graphs or complex networks, the neighborhood of a cell (or node) is determined by the edges connecting it to other cells (or nodes). This allows for the study of cellular automata on non-regular and non-uniform topologies.

References

• Culik II, K., & Yu, S. (2003). Cellular automata. In J. van Leeuwen (Ed.), Handbook of Theoretical Computer Science (Vol. B, pp. 179-262). MIT Press.

• Bagnoli, F. (2005). Complex Systems and Artificial Life. In A. Adamatzky (Ed.), Collision-Based Computing (pp. 11-53). Springer.

• Chopard, B. (2002). Cellular Automata Modeling of Physical Systems. Cambridge University Press.

• Formenti, E. (2010). Cellular Automata. In J. Gruska, J. Zlatuska, & V. Koubek (Eds.), Mathematical Foundations of Computer Science 2010 (pp. 15-37). Springer.

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

• Imai, K., Grassberger, P., & Fatès, N. (1999). Exact scaling properties of directed percolation in two dimensions. Journal of Physics A: Mathematical and General, 32(44), 7111-7125.

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

• Israeli, Navot and Goldenfeld, Nigel (2006). Coarse-graining of cellular automata, emergence, and the predictability of complex systems, Phys. Rev. E 73, 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., & Guillon, P. (1998). Cellular automata and groups. Journal of Statistical Physics, 93(1-2), 31-57.

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

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

• Stepney, S. (2003). Cellular automata as unconventional computers. In L. Nadel & D. Stein (Eds.), Unconventional Computation (pp. 391-417). Springer.

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

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

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

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

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

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

• Adamatzky, Andrew (1994). Hierarchy of fuzzy cellular automata, Fuzzy Sets and Systems, vol. 62:2, pp. 167-174.

• Adamatzky, Andrew (1996). Voronoi-like partition of lattice in cellular automata, Mathematical and Computer Modelling, vol 23:4 pp 51-66.

• Adamatzky, Andrew (1996). Computation of shortest path in cellular automata, vol 23:4, pp. 105-113, Mathematical and Computer Modelling.

• Adamatzky, Andrew and Wuensche, Andrew and De Lacy Costello, Benjamin (2006). Glider-based computing in reaction-diffusion hexagonal cellular automata, Chaos, Solitons & Fractals, vol. 27:2 pp. 287-295.

• Adamatzky, Andrew and Martínez J., Genaro and Seck Tuoh Mora, Juan Carlos (2006). Phenomenology of reaction–diffusion binary-state cellular automata, International Journal of Bifurcation and Chaos, 16:10, pp. 2985-3005.

• Adamatzky, Andrew and Wuensche, Andrew (2006). Computing in spiral rule reaction-diffusion hexagonal cellular automaton, Complex Systems, vol. 16:4, pp. 277-298.

• Amoroso, Serafino; Patt, Yale N. (1972). Decision Procedures for Surjectivity and Injectivity of Parallel Maps for Tessellation Structures. J. Comput. Syst. Sci. 6 (5): 448–464. doi:10.1016/s0022-0000(72)80013-8.

• Burton H. Voorhees (1996). Computational analysis of one-dimensional cellular automata. World Scientific. p. 8. ISBN 978-981-02-2221-5.

• Durand-Lose, Jérôme (2001). Representing reversible cellular automata with reversible block cellular automata. Discrete Mathematics and Theoretical Computer Science. AA: 145–154. Archived from the original on 15 May 2011.

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

• Fredkin, Edwin (1990). Digital mechanics: an informational process based on reversible universal cellular automata, Physica D 45, 254–270.

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

• Grassberger, P. (1986). Toward a Quantitative Theory of Self-Generated Complexity. International Journal of Theoretical Physics, 25(9), 907-938. [This paper discusses the use of Lyapunov exponents to characterize the complexity and chaos in cellular automata.]

• Gardner, Martin (1970). Mathematical Games: The fantastic combinations of John Conway's new solitaire game life. Scientific American. 223 (223): 120–123. doi:10.1038/scientificamerican1070-120.

• Green, D. G. (1994). Connectivity and complexity in landscapes and ecosystems. Pacific Conservation Biology, 1(3), 194–200.

• 't Hooft, Gerard 2016, The Cellular Automaton Interpretation of Quantum Mechanics, Springer International Publishing, DOI 10.1007/978-3-319-41285-6

• Ilachinski, Andrew (2001). Cellular automata: a discrete universe. World Scientific. ISBN 978-981-238-183-5.

• Kari, Jarkko (1990). Reversibility of 2D cellular automata is undecidable. Physica D. 45 (1–3): 379–385. doi:10.1016/0167-2789(90)90195-U.

• Kari, Jarkko (1999). On the circuit depth of structurally reversible cellular automata. Fundamenta Informaticae. 38: 93–107.

• Kari, Jarkko (2005). Theory of cellular automata: a survey. Theoret. Comp. Sci., 334:3–33.

• Li, Wentian; Packard, Norman (1990). The structure of the elementary cellular automata rule space. Complex Systems. (4) 281–297.

• Martínez G. Juarez, Adamatzky Andrew and McIntosh V. Herald (2006). Phenomenology of glider collisions in cellular automaton Rule 54 and associated logical gates, Chaos, Solitons & Fractals, vol. 28:1, pp. 100-111.

• Martinez, Genaro J. and Adamatzky, Andrew and Alonso-Sanz, Ramon (2012). Complex dynamics of elementary cellular automata emerging from chaotic rules, International Journal of Bifurcation and Chaos, 22:02 pp. 1250023.

• Martinez, Genaro J. and Adamatzky and Stephens, Christian R, and Hoeflich, AF (2011). Cellular automaton supercolliders, International Journal of Modern Physics C, 22:04 pp. 419-439.

• Margenstern, Maurice (2007). Cellular Automata in Hyperbolic Spaces – Tome I, Volume 1, Old City Pub Inc; First Edition.

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

• Nicolis (1974). Dissipative Structures, Catastrophes, and Pattern Formation: A Bifurcation Analysis. PNAS. 71 (7): 2748–2751.

• Packard, N. H. (1988). Adaptation Toward the Edge of Chaos. In J. A. S. Kelso, A. J. Mandell, & M. F. Shlesinger (Eds.), Dynamic Patterns in Complex Systems (pp. 293-301). World Scientific.

• Riedel, Jürgen and Zenil, Hector (2018). Rule Primality, Minimal Generating Sets and Turing-Universality in the Causal Decomposition of Elementary Cellular Automata. Journal of Cellular Automata, vol. 13, pp. 479-497.

• Riedel, Jürgen and Zenil, Hector (2018). Cross-boundary Behavioural Reprogrammability Reveals Evidence of Pervasive Universality. International Journal of Unconventional Computing, vol 13:14-15 pp. 309-357.

• Sutner, Klaus (1991). De Bruijn Graphs and Linear Cellular Automata. Complex Systems. 5: 19–30.

• Smith, Alvy Ray (1971). Cellular Automata Complexity Trade-Offs, Information and Control, vol. 18:5 pp 466-482.

• Smith, Alvy Ray (1971). Simple Computation-Universal Cellular Spaces Journal of the ACMVolume 18:301 pp 339–353.

• Smith, Alvy Ray (1976). Simple Nontrivial Self-Reproducing Machines, In: Artificial Life II (Langton, C. G., Taylor, C., Farmer, J. D. and Rasmussen, S., eds.) (Vol. X of SFI Studies in the Sciences of Complexity) (Addison-Wesley, Redwood City, CA, 1992) pp. 709–725.

• Smith, Alvy Ray. Introduction to and Survey of Cellular Automata or Polyautomata Theory. In Automata, Languages, Development, eds. A. Lindenmayer and G. Rozenberg, North-Holland Publishing Co., New York, 405-422.

• Reisinger, Drew and Martin, Taylor and Blankenship, Mason and Harrison, Christopher and Squires, Jesse and Beavers, Anthony, Exploring Wolfram’s Notion of Computational Irreducibility with a Two-Dimensional Cellular Automaton (2012) In Zenil, Hector (Ed.) Irreducibility and Computational Equivalence: 10 Years After Wolfram's A New Kind of Science, Springer, Heidelberg.

• Sutner, Klaus (2012) Computational Equivalence and Classical Recursion Theory. In Zenil, Hector (Ed.) Irreducibility and Computational Equivalence: 10 Years After Wolfram's A New Kind of Science, Springer, Heidelberg.

• Toffoli, Tommaso and Margolus, Nornam (1987) Cellular Automata Machines: A New Environment for Modeling. Cambridge, MA: MIT Press.

• Toom, A. (1991). Stable and attractive trajectories in multicomponent systems. In Multicomponent Random Systems (pp. 549–575). Springer.

• von Neumann, John (1951). The general and logical theory of automata, in L.A. Jeffress, ed., Cerebral Mechanisms in Behavior – The Hixon Symposium, John Wiley & Sons, New York, pp. 1–31.

• Weisstein, E. W. Books about Cellular Automata. http://www.ericweisstein.com/encyclopedias/books/CellularAutomata.html.

• Wolfram, Stephen Statistical Mechanics of Cellular Automata. Rev. Mod. Phys. 55, 601-644, 1983.

• Wolfram, Stephen Twenty Problems in the Theory of Cellular Automata. Physica Scripta T9, 170-183, 1985.

• Wolfram, Stephen (Ed.). Theory and Application of Cellular Automata. Reading, MA: Addison-Wesley, 1986.

• Wolfram, Stephen Cellular Automata and Complexity: Collected Papers. Reading, MA: Addison-Wesley, 1994.

• Wolfram, Stephen A New Kind of Science. Champaign, IL: Wolfram Media, 2002.

• Wolfgang, A. (1995). Cryptography and data security: cryptographic properties of cellular automaton rules. Complexity, 1(1), 49–56.

• Wuensche, Andrew and Lesser, M. The Global Dynamics of Cellular Automata: An Atlas of Basin of Attraction Fields of One-Dimensional Cellular Automata. Reading, MA: Addison-Wesley, 1992.

• Wuensche, Andrew and Adamatzky, Andrew (2006) On spiral glider-guns in hexagonal cellular automata: activator-inhibitor paradigm, International Journal of Modern Physics C, vol. 17:07, pp. 1009-1026.

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

• Zenil, Hector (2013), “Asymptotic behavior and ratios of complexity in cellular automata,” International Journal of Bifurcation and Chaos, vol. 23, no. 9, Article ID 1350159.

• Zenil, Hector (2012) Irreducibility and Computational Equivalence: 10 Years After Wolfram's A New Kind of Science, Springer, Heidelberg.

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

• Zenil, Hector (2012) A Computable Universe, World Scientific Publishing Company.

• Zuse, Konrad (1982). The Computing Universe, Int. Jour. of Theo. Phy. 21, 589–600.

• Zuse, Konrad (1970) Calculating Space, MIT Technical Translation AZT-70-164-GEMIT, Massachusetts Institute of Technology (Project MAC), Cambridge, Mass. 02139. Adrian German and Hector Zenil (eds). In Zenil, Hector (2012) A Computable Universe, World Scientific Publishing Company.

• Zwirn, Hervé (2013) Computational Irreducibility and Computational Analogy, Complex Systems 24(2).

• Zwirn, Hervé and Delahaye, Jean-Paul (2012) Unpredictability and Computational Irreducibility. In Zenil, Hector (Ed.) Irreducibility and Computational Equivalence: 10 Years After Wolfram's A New Kind of Science, Springer, Heidelberg.