Cyclic cellular automaton

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. == One dimension ==

The one-dimensional cyclic cellular automaton has been extensively studied by Robert Fisch, a student of Griffeath. 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. The long-term behavior of this rule is exactly solvable. If two of the three values each have an initial density of 0 ≤ p ≤ 1/2, then at time t the mean cluster size is asymptotically equal to \sqrt{\pi t / 2 p}. 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. Beginning at an initial state with equal densities for all values, the mean cluster size obeys a power law with exponent around 0.3467. However, for n ≥ 5, random initial configurations tend to stabilize quickly rather than forming any non-trivial long-range dynamics. 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. == Two or more dimensions ==

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. 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. The demons with shorter cycles consume demons with longer cycles until, 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-periodic behavior occurs also in higher dimensions. Small structures can also be constructed with any even period between n and 3n/2. Merging these structures, configurations can be built with a global super-polynomial period. 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. 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, or other systems of autowaves, although other cellular automata more accurately model the excitable medium that leads to this reaction. ==Notes==