Cyclic, Greenberg–Hastings and rock-paper-scissors

These three families share one idea: states arranged in a cycle, where each state can be overtaken only by the next one around. From a random start they organise themselves into travelling waves and rotating spirals, the same patterns seen in chemical oscillators, heart tissue and competing species. JETCARP runs all three on any tiling.

What it is

Cyclic cellular automaton. There are n colours arranged on a wheel, 0, 1, …, n − 1 and back to 0. A cell of colour k changes to colour k + 1 (mod n) when at least a threshold number of its neighbours already have colour k + 1; otherwise it stays. Every colour is “eaten” by the next. From random colours, the grid first breaks into patches, then small cycles of colours that chase each other around a point appear, and these spiral cores, once formed, take over the whole grid.

Greenberg–Hastings. A model of an excitable medium. A cell is resting (0), excited (1), or in one of several refractory stages (2 to n − 1). A resting cell becomes excited when at least a threshold number of its neighbours are excited; every other state advances one step on its own, the last refractory stage returning to rest. An excited region therefore fires once and cannot fire again for a while, so excitation travels as waves that annihilate when they meet. In the cyclic automaton every state needs a neighbour to advance; in Greenberg–Hastings only the resting state does (Fisch, Gravner and Griffeath 1991).

Rock-paper-scissors. Each cell is one of n species in a cycle of dominance (with three: rock, paper, scissors). A cell is taken over by its predator, the next species around the cycle, when more than a threshold number of its neighbours are that predator. This is a cyclic automaton with a strict threshold: RPS n/t behaves like Cyclic n/(t+1).

Where it came from

Greenberg–Hastings (1978). J. M. Greenberg and S. P. Hastings introduced their discrete model of excitable media in 1978 (Greenberg and Hastings 1978), and the same year Greenberg, Hassard and Hastings surveyed pattern formation in reaction–diffusion systems (Greenberg, Hassard and Hastings 1978). The model belongs to the tradition of excitable media such as nerve and heart tissue and the Belousov–Zhabotinsky reaction. Rigorous results followed from Durrett and Steif (1991), Fisch, Gravner and Griffeath (1993) and Durrett and Griffeath (1993).

The cyclic automaton (late 1980s). The cyclic cellular automaton came from David Griffeath’s probability group at the University of Wisconsin–Madison; MCell’s documentation says it was discovered and explored by Griffeath (MCell families). Griffeath described it in “Cyclic random competition” in the Notices of the AMS in December 1988 (Griffeath 1988); its random ancestor is the cyclic particle system of Bramson and Griffeath (1989). Griffeath’s student Robert Fisch analysed the one-dimensional version (Fisch 1990; Fisch 1990b). A. K. Dewdney presented the two-dimensional rule as “cyclic space” in Scientific American in August 1989; the “demons” of Dewdney’s title are the spiral cores (Dewdney 1989). The standard reference, which treats the cyclic and Greenberg–Hastings rules together with a range and a threshold, is Fisch, Gravner and Griffeath’s “Threshold-range scaling of excitable cellular automata” (1991).

Rock-paper-scissors. Three species in a cycle of dominance on a lattice have been studied in physics and ecology since Kei-ichi Tainaka’s lattice Lotka–Volterra models (Tainaka 1988; Tainaka 1989), including Frean and Abraham’s “survival of the weakest” (2001), Kerr, Riley, Feldman and Bohannan’s experiment with strains of E. coli (2002), and Reichenbach, Mobilia and Frey’s work on mobility and spiral waves (2007). Those models are stochastic. The deterministic threshold rule JETCARP implements is the one described by Softology, maker of Visions of Chaos, in a 2018 blog post (Softology 2018).

How JETCARP runs it

Notation

The cyclic automaton uses edge neighbours by default, the four orthogonal neighbours on squares; Greenberg–Hastings and rock-paper-scissors use touch neighbours. Either can be changed per automaton. With edge neighbours and threshold 1, as in the cyclic figures, spirals form readily. Starting patterns are usually random states (random_states).

On any tiling

All three families only count neighbours in particular states, so they run on any neighbour graph (see How JETCARP generalises automata). The spirals change shape with the tiling: square on squares, rounder on hexagons, irregular on Penrose and hat tilings, but they still form. Greenberg–Hastings worlds on lattice tilings can be jumped far ahead with HashLife.

What is new here

Cyclic automata have been run on general networks before: Yiqing Cai and Robert Ghrist studied cyclic automata on sensor networks and the waves they carry (Cai and Ghrist 2014). Our prior-art search found no earlier version of these three families on aperiodic tilings such as Penrose, hat or spectre, but that is a direct application of known rules to known graphs, so we do not count it as a discovery.

Try it

• Quick Start: Cyclic CA, Greenberg-Hastings and Rock-paper-scissors.
• jetcarp run docs/scenes/automata/cyclic-hat.json --gens 600 --png spirals.png
• Raise the threshold of Cyclic 16/1 to 2 or 3 with touch neighbours: Fisch, Gravner and Griffeath mapped how range and threshold decide between spirals, turbulence and fixation.

References

• Greenberg and Hastings 1978; Greenberg, Hassard and Hastings 1978; Durrett and Steif 1991; Fisch, Gravner and Griffeath 1993; Durrett and Griffeath 1993
• Griffeath 1988; Bramson and Griffeath 1989; Fisch 1990; Fisch 1990b; Dewdney 1989; Fisch, Gravner and Griffeath 1991; MCell families; Cai and Ghrist 2014
• Tainaka 1988; Tainaka 1989; Frean and Abraham 2001; Kerr et al. 2002; Reichenbach, Mobilia and Frey 2007; Softology 2018