A one-dimensional cyclic cellular automaton with n = 4, run for 300 steps from a random initial configuration.

The cyclic cellular automaton is a cellular automaton rule developed by Robert Fisch and studied by several other cellular automaton researchers. In this system, each cell remains unchanged until some neighboring cell has a value one unit larger than that of the cell itself, at which point it copies its neighbor's value. One-dimensional cyclic cellular automata can be interpreted as systems of interacting particles, while cyclic cellular automata in higher dimensions exhibit complex spiraling behavior. A cellular automaton (plural: cellular automata) is a discrete model studied in computability theory, mathematics, and theoretical biology. ...

Rules

As with any cellular automaton, the cyclic cellular automaton consists of a regular grid of cells in one or more dimensions. The cells can take on any of n states, ranging from 0 to n − 1. The first generation starts out with random states in each of the cells. In each subsequent generation, if a cell has a neighboring cell whose value is the successor of the cell's value, the cell is "consumed" and takes on the succeeding value. (Note that 0 is the successor of n − 1; see also modular arithmetic.) More general forms of this type of rule also include a threshold parameter, and only allow a cell to be consumed when the number of neighbors with the successor value exceeds this threshold. Modular arithmetic (sometimes called modulo arithmetic, or clock arithmetic because of its use in the 24-hour clock system) is a system of arithmetic for integers, where numbers wrap around after they reach a certain value — the modulus. ...

One dimension

The one-dimensional cyclic cellular automaton has been extensively studied by Fisch.^[1] Starting from a random configuration with n = 3 or n = 4, this type of rule can produce a pattern which, when presented as a time-space diagram, shows growing triangles of values competing for larger regions of the grid.

The boundaries between these regions can be viewed as moving particles which collide and interact with each other. In the three-state cyclic cellular automaton, the boundary between regions with values i and i + 1 (mod n) can be viewed as a particle that moves either leftwards or rightwards depending on the ordering of the regions; when a leftward-moving particle collides with a rightward-moving one, they annihilate each other, leaving two fewer particles in the system. This type of ballistic annihilation process occurs in several other cellular automata and related systems, including Rule 184, a cellular automaton used to model traffic flow.^[2] Annihilation is defined as total destruction or complete obliteration of an object;[1] having its root in the Latin nihil (nothing). ... The mathematical study of traffic flow, and in particular vehicular traffic flow, is done with the aim to get a better understanding of these phenomena and to assist in prevention of traffic congestion problems. ...

In the n = 4 automaton, the same two types of particles and the same annihilation reaction occur. Additionally, a boundary between regions with values i and i + 2 (mod n) can be viewed as a third type of particle, that remains stationary. A collision between a moving and a stationary particle results in a single moving particle moving in the opposite direction.

However, for n ≥ 5, random initial configurations tend to stabilize quickly rather than forming any non-trivial long-range dynamics. David Griffeath has nicknamed this dichotomy between the long-range particle dynamics of the n = 3 and n = 4 automata on the one hand, and the static behavior of the n ≥ 5 automata on the other hand, "Bob's dilemma", after Bob Fisch.^[3]

Two or more dimensions

A two-dimensional cyclic cellular automaton with n = 16, after 400 steps starting from a random initial configuration. All three types of patterns formed by this automaton are visible in this image.

In two dimensions, with no threshold and the von Neumann neighborhood or Moore neighborhood, this cellular automaton generates three general types of patterns sequentially, from random initial conditions on sufficiently large grids, regardless of n.^[4] At first, the field is purely random. As cells consume their neighbors and get within range to be consumed by higher-ranking cells, the automaton goes to the consuming phase, where there are blocks of color advancing against remaining blocks of randomness. Important in further development are objects called demons, which are cycles of adjacent cells containing one cell of each state, in the cyclic order; these cycles continuously rotate and generate waves that spread out in a spiral pattern centered at the cells of the demon. The third stage, the demon stage, is dominated by these cycles. Almost surely, every cell of the automaton eventually enters a repeating cycle of states, where the period of the repetition is either n or (for automata with n odd and the von Neumann neighborhood) n + 1. The same eventually-period behavior occurs also in higher dimensions. This article does not cite its references or sources. ... In mathematics, specifically, in probability theory, the phrase almost surely is a concise, precise way to state except on a set or event of probability measure zero. ...

For larger neighborhoods, similar spiraling behavior occurs for low thresholds, but for sufficiently high thresholds the automaton stabilizes in the block of color stage without forming spirals. At intermediate values of the threshold, a complex mix of color blocks and partial spirals, called turbulence, can form.^[5] For appropriate choices of the number of states and the size of the neighborhood, the spiral patterns formed by this automaton can be made to resemble those of the Belousov-Zhabotinsky reaction in chemistry, although other cellular automata more accurately model the excitable medium that leads to this reaction. In fluid dynamics, turbulence or turbulent flow is a flow regime characterized by chaotic, stochastic property changes. ... A Belousov-Zhabotinsky reaction, or BZ reaction, is one of a class of reactions that result in the establishment of a nonlinear chemical oscillator. ... An excitable medium is a nonlinear dynamical system which has the capacity to propagate a wave of some description, and which cannot support the passing of another wave until a certain amount of time has passed (known as the refractory time). ...

Notes

References

• Belitzky, Vladimir; Ferrari, Pablo A. (1995). "Ballistic annihilation and deterministic surface growth". Journal of Statistical Physics 80 (3–4): 517–543. DOI:10.1007/BF02178546. 

• Bunimovich L. A.; Troubetzkoy, S. E. (1994). "Rotators, periodicity, and absence of diffusion in cyclic cellular automata". Journal of Statistical Physics 74 (1–2): 1–10. DOI:10.1007/BF02186804. 

• Fisch, R. (1990a). "The one-dimensional cyclic cellular automaton: A system with deterministic dynamics that emulates an interacting particle system with stochastic dynamics". Journal of Theoretical Probability 3 (2): 311–338. DOI:10.1007/BF01045164. 

• Fisch, R. (1990b). "Cyclic cellular automata and related processes". Physica D 45 (1–3): 19–25. DOI:10.1016/0167-2789(90)90170-T. 

• Fisch, R. (1992). "Clustering in the one-dimensional three-color cyclic cellular automaton". Annals of Probability 20 (3): 1528–1548. 

• Fisch, R.; Gravner, J.; Griffeath, D. (1991). "Threshold-Range Scaling of Excitable Cellular Automata". Statistics and Computing 1: 23–39. DOI:10.1007/BF01890834. 

• Shalizi, Cosma Rohilla; Shalizi, Kristina Lisa (2003). "Quantifying self-organization in cyclic cellular automata". Lutz Schimansky-Geier, Derek Abbott, Alexander Neiman and Christian Van den Broeck (eds.) Noise in Complex Systems and Stochastic Dynamics: 108–117, Bellingham, Washington: SPIE. arXiv:nlin/0507067. 

• Steif, Jeffrey E. (1995). "Two applications of percolation to cellular automata". Journal of Statistical Physics 78 (5–6): 1325–1335. DOI:10.1007/BF02180134.