Greenberg–Hastings cellular automaton

Informal description

As in a typical two dimensional cellular automaton, consider a rectangular grid, or checkerboard pattern, of "cells". It can be finite or infinite in extent. Each cell has a set of "neighbors". In the simplest case, each cell has four neighbors, those being the cells directly above or below or to the left or right of the given cell.

Like this: the b's are all of the neighbors of the a. The a is one of the neighbors of each of the b's.

b b a b b

At each "time" t=0,1,2,3,...., each cell is assigned one of three "states", typically called "resting" (or "quiescent" ; see excitable medium), "excited", or "refractory". The assignment of states for all cells is arbitrary for t = 0, and then at subsequent times the state of each cell is determined by the following rules.

1. If a cell is in the excited state at time t then it is in the refractory state at time t+1.

2. If a cell is in the refractory state at time t then it is in the resting state at time t+1.

3. If a given cell is in the resting state at time t, and at least one of its neighbors is in the excited state at time t, then the given cell is in the excited state at time t+1. If a cell is in the resting state at time t and no neighbor is excited at time t, then the given cell is still in the resting state at time t+1.

In this way the whole grid of cells advances from their initial states at t = 0 to their states at t = 1, then to their states at t = 2,3,4, etc., producing a pattern of cells in the various states for each time.

See the first animation in Belousov-Zhabotinsky reaction for a striking example of behavior that can be exhibited by this model. The three states are indicated by different colors.

Mathematical description

To describe the GH model more mathematically, consider the simplest case of a grid of square cells C i , j . At each time t = 0 , 1 , 2 , . . . the cell C i , j has a state S i , j t ∈ { 0 , 1 , 2 } . The type of neighborhood is not important, so long as each cell has some neighbors. In a square grid (as opposed to hexagonal), either four or eight cell neighborhoods work fine. The evolution rule is as follows: If S i , j t = 1 then S i , j t + 1 = 2 . If S i , j t = 2 then S i , j t + 1 = 0. If S i , j t = 0 and S i ′ , j ′ t = 1 for some neighboring cell C i ′ , j ′ , then S i , j t + 1 = 1 . Otherwise, S i , j t + 1 = 0.

Relation to a model of Wiener and Rosenblueth

While the GH model has often been compared with the ground breaking model of Wiener and Rosenblueth developed earlier for the same purpose, the analogy is incomplete because the latter is not a CA. See for example, in which it is stated that "The organization of muscle cells, the contraction of muscle, the dependence of the activity of the medium on the activity of its component elements, problems of memory, reliability, and mobility were formulated by Wiener in the form of definitions and theorems for a three- phase threshold-invariant continuous excitable medium." In other words, as is easily seen by consulting the original paper, the "state" is discrete, but time and the medium in which activity propagates are continuous, resulting in wave fronts which are continuous curves.

Further on in it is stated that

"Automaton models of excitable media were investigated in [9] and [10]. These models are a discrete analog of Wiener's medium." (The models in their citations "[9]" and "[10]" are different from GH.)

Many writers have called the Weiner-Rosenblueth model a cellular automaton. The earliest paper found by Google Scholar with this designation clearly stated is. However, as mentioned above, the continuity of the Wiener-Rosenblueth medium has not so far allowed as precise a theorem about persistence of patterns as the one for GH which is described below. On the other hand, several theorems are stated in which are similar to those proved in, though the proofs given for the theorems in are less clear than those in because of the natures of the respective models.

See also for an often cited computer study based on a model which is similar to that of Wiener and Rosenblueth.

Generating a spiral

One interesting behavior is seen, for a four cell neighborhood and a square grid, when the initial condition consists of a half line of excited cells (1's) going off to infinity and below this half line a half line of refractory cells (2's). The rest of the cells are resting when t=0.

Like this:

................................................................... ....00000000000000000000000000000000000000000000000000000000000.... ....00000000000000000000000000000000000000000000000000000000000.... ....00000000000000000001111111111111111111111111111111111111111.... ....00000000000000000002222222222222222222222222222222222222222.... ....00000000000000000000000000000000000000000000000000000000000.... ....00000000000000000000000000000000000000000000000000000000000.... ...................................................................

The spiral which is produced can be seen in. This spiral can easily be seen by following the pattern forward for a few iterations "by hand". No computer is necessary.

A theorem

As stated in, and proved in (which also considered n-state models), if the set of initial 1's is finite, then every individual cell oscillates forever through the cycle 0,1,2,0 if and only if at the start there is at least one square of four neighboring cells with one of the following patterns:

1 2 2 0 0 1 0 0 1 1 2 2

or some reflection or rotation of one of these. These patterns cannot be killed off by their surroundings. It is the "only if" part of this result which is most interesting. If none of these patterns is present at t = 0, then in any bounded region the pattern eventually settles down to all zeros. The key tool in the proof in is a "winding number" which is shown to be invariant for this model.

One easy consequence of the theorem stated above is that if there are no "refractory" cells initially then the pattern will die out in any bounded region (whether the total grid is finite or infinite in extent). This property of an excitable medium was found earlier, in the paper of Wiener and Rosenblueth, and does not hold if there are "holes" in the region.