Cellular Automata rules lexicon

Go back to MCell Home

Family: Cyclic CA

Type: cyclic totalistic

Cyclic Cellular Automata (CCA) exhibit complex self-organization by iteration of an extremely simple update rule. A specified # of Colors are arranged cyclically in a "color wheel." Each color can only advance to the next, the last cycling to 0. Each update a cell's color advances by 1 if there are at least Threshold cells of the next color within its neighbour set of size Range in extended Moore or von Neumann neighbourhood. These simple dynamics exhibit complex self-organization starting from randomness. This class of CAs was discovered and explored by David Griffeath (http://psoup.math.wisc.edu/kitchen.html).

The MCell's implementation of CCA features also a special case of CCA - the Greenberg-Hastings (GH) Model, perhaps the simplest CA prototype for an excitable medium. A prescribed number of colors N are arranged cyclically in a "color wheel." Each color can only advance to the next, the last cycling to 0. Every update, cells change from color 0 (resting) to 1 (excited) if they have at least Threshold 1's in their neighbor set. All other colors (refractory) advance automatically. Starting from a uniform random soup of the available colors, the excitation dies out if the threshold is too large compared to the size of the neighbor set, while a disordered soup virtually indistinguishable from noise results if the threshold is too low. For intermediate thresholds, however, waves of excitation self-organize into large-scale spiral pairs that stabilize in a locally periodic state.

Cyclic CA notation

The notation of Cyclic Cellular Automata has the "R/T/C/N" form, where:
R - specifies the neighbourhood range (1..10).
T - specifies the threshold - minimal count of cells in the neighbourhood having the next color, necessary for the cell to advance to the next state.
C - specifies the count of states in the rule (0..C-1).
N - specifies the neighbourhood type: NM stands for extended Moore, NN for extended von Neumann.

Range 'R' von Neumann neighborhood includes all sites which can be reached from the origin in at most R steps by N, S, E and W moves, whereas range 'R' Moore neighbourhood also allows NE, SE, NW and SW moves at each step.

In general Cyclic CA rules should be started from uniformly randomized boards.

MJCell Java applet is able to run all rules from this group.

MCell built-in Cyclic CA rules

Name Rule (R/T/C/N) Character Description
313 R1/T3/C3/NM Cyclic "This is the only three-color rule in the range-1 CCA rulespace that exhibits significant self-organization. And it's no slouch in that regard, either. It sports a number of distinct spiral types, its demographics are eminently watchable, and in general it has a flavor all its own." - J.Elliott
A rule by David Griffeath.
3-color bootstrap R2/T11/C3/NM Cyclic The term bootstrap refers to systems with local clusters which can only propagate by means of external support from random noise or other clusters. Such critical dynamics, and related near-critical rules, often fixate in complex 'fossilized' final configurations. This rule shows a 3-color CCA with competing bootstrap growth.
A rule by David Griffeath.
Amoeba R3/T10/C2/NN Stable Similar to Vote 4/5, this rule smoothes patterns and leaves irregular islands with characteristic oscillating edges.
A rule by Jason Rampe.
Black vs White R5/T23/C2/NN Chaotic Well-balanced rule where both death (black) and life (white) have equal chances. Seed patterns with 50% density.
A rule by Jason Rampe.
CCA R1/T1/C14/NN Cyclic A basic CCA. Starting from a uniform random distribution over 14 colors, droplets of color waves nucleate fairly quickly. Soon virtually all of the initial "debris" are overrun by the droplets. As the last vestiges of debris are eliminated, vortices emerge from the disordered wave fronts, creating diamond-shaped spirals. By about time 300 the array is completely covered with periodic spirals, out of phase with one another and not all of minimal period 14. Typically it takes much longer for the period 14 spiral cores to displace their feebler competitors.
A rule by David Griffeath.
Cubism R2/T5/C3/NN Stable This interesting rule creates rectangular regions.
A rule by Jason Rampe.
Cyclic spirals R3/T5/C8/NM Cyclic A rule by David Griffeath.
Fossil debris R2/T9/C4/NM Cyclic A rule by David Griffeath.
GH Macaroni R2/T4/C5/NM/GH Cyclic The threshold is sufficiently high that wave fragments have a hard time bending inwards to make spiral cores. Consequently, cyclic bands self-organize over time into weakly aligned parades of wave fragments. The pattern is not unlike that of the monolayer of macaroni that adheres to a colander during the preparation of a $.059 box of macaroni and cheese. CAM6 experiments have revealed that if these dynamics are allowed to run for thousands of updates on a larger array, say 2048 by 2048, then the wave fragments continue to align into ever longer parades. But more than this, the pasta also merge end to end until they transform into a new variety: spaghetti. We expect that on an infinite array the process would continue to enormous length scales, giving rise to linguine, then angel hair, then ...
A rule by David Griffeath.
GH Multistrands R5/T15/C6/NM/GH Cyclic A rule by David Griffeath.
GH Percolation mix R5/T10/C8/NM/GH Cyclic With larger neighbor sets and low thresholds, stable periodic cycles occur by chance in the initial random soup. Thus one encounters a mixture of partial self-organization and percolation effects.
A rule by David Griffeath.
GH Weak spirals R4/T9/C7/NM/GH Cyclic A rule by David Griffeath.
GH R3/T5/C8/NM/GH Cyclic A basic Greenberg-Hastings model.
A rule by David Griffeath.
Imperfect R1/T2/C4/NM Cyclic From Elliott's description: "A little magic carpet generator of cellsize 4. One thing that sets this rule apart from other CCAs I know of is a phenomenon that occurs in the occasional orbit, in which a garish living stain forms and grows till it blots out the entire carpet. This cancerous growth (to mix my metaphors) starts from a small anomalous patch of cells - though not inevitably, for some such tumors are benign. So, in a way this rule reverses the situation we encounter in its higher threshold cousin, Perfect. In the latter rule, regular spirals invade a "broken" but seemingly stable dynamic, whereas here the tables are turned and it is an orderly spiral regime that finds itself overthrown."
A rule by John Elliott, May 2000.
LavaLamp R2/T10/C3/NM Cyclic The rule produces blobs that seperate and combine resembling a lava lamp.
A rule by Jason Rampe.
Maps R2/T3/C5/NN Cyclic A rule by Mirek Wojtowicz.
Perfect R1/T3/C4/NM Cyclic A particularly interesting excitable system. From a uniform random configuration it quickly self-organizes into a chaotic soup with large length scale. But later on, often after more than one hundred updates, perfect, widely separated stable spiral cores emerge and slowly take over the lattice.
A rule by David Griffeath.
Squarish Spirals R2/T2/C6/NN Chaotic A rule by Jason Rampe.
Stripes R3/T4/C5/NN Cyclic A rule by Mirek Wojtowicz.
Turbulent phase R2/T5/C8/NM Cyclic When the threshold is high enough that wave fronts cannot wind, but still low enough that they can advance, CCA rules exhibit a chaotic equilibrium phase which combines the small-scale structure of failed cores with large-scale disordered fronts. Our animations give only a glimpse of this behavior, since the typical final length scale of several hundred cells means that large arrays are needed to support a viable steady state. Small systems inevitably fixate. Note how impossible it is to predict, until the very end, which color will predominate.
A rule by David Griffeath.

 


Webmaster: Mirek Wójtowicz
envelope info@mirekw.com,
envelope mirwoj@life.pl
globe http://www.mirekw.com


MCell mirrors:
globe USA  http://psoup.math.wisc.edu/mcell/
globe Europe  http://www.mirwoj.opus.chelm.pl

Last update: 15 Sep 2001