Cellular automata

An interesting example of recursive systems are cellular automata (CAs). Formally these are a class of spatially and temporally discrete, deterministic mathematical systems characterized by local interaction and inherently parallel form of evolution. The basic idea of CAs is to regard the development of cells that change their state (for example from \(0\) to \(1\) or from white to black) in dependence of the state of neighboring cells. This change is determined by rules like the following:

Example-rule: Whenever a white (or a \(0\)-) cell has a majority of black (or \(1\)-) cells as neighbors it turns black (or \(1\)) in the next step of time.

Elementary cellular automata

Elementary (or one-dimensional) cellular automata, as Stephen Wolfram (1983, 2002) began to study them in the 1980ies, consist of a set of cells arranged on a brace (as shown in the first row in the cell grid beneath to the right), with each of the cells being able to take on two states, e.g. black or white. A cell together with its two neighbors to the left and to the right is called a neighborhood. Initially (at time \(t=0)\) each cell is assigned a random state - either black or white ( or \(0\) or \(1\) ) - that changes in each time step in dependence of the cell states in the neighborhood. Determining factors are rules that arise from the possible combinations of ones and zeros in a neighborhood of three. Usually these rules are depicted by way of a look-up table (beneath to the left) that reads in the following way: A cell \(X\) in time \(t\) looks at its own state and at the state of its left and right neighbors and then, in time \(t + 1\), takes on the state as indicated in the respective row of the last column in the table. Applying this to all cells in a row generates a next generation of cells in the next lower row to which the same procedure is applied recursively. In the following interactive model this is done by the computer until the bottom row of the cell grid is reached (mouse-clicking into the grid or moving the sliders restarts the model with a new randomly generated first row).

The binary number in column \(X_{t+1}\), when read bottom-up and interpreted as a decimal, labels the rule. The first slider above changes the rule. The second slider allows changing the cell size.

Note that the emerging patterns can span cell-aggregations larger than the three cells originally considered in the rule. Obviously local interactions can generate structures (or order) with not-just-local (i.e. global or near-global) scope. These structures do not seem to be predictable from the rules. They are a typical example of the counter-intuitive behavior systems can show. They are a case of emergent behavior. The whole seems to be more than the sum of its parts.

Elementary CAs have a state space of size \(2^8 = 256\). The combination of three neighbors, which can take on two states each, gives a state space of \(2^3 = 8\) possible combinations, with the resulting \(8\) positions again consisting of two states each resulting in a state space of: \(2^8 = 256\).

The general formula for calculating CA state spaces is: \(n^{(n^k)}\) with \(k =\) neighbors and \(n =\) states.

CA classes, according to Stephen Wolfram

CAs follow deterministic rules (no deviation, no probability allowed). This means that even if the state space is huge, once it is filled, a CA starts to repeat its patterns. Depending on the particular rule of a CA, this point of recurrence might be as far away as the complete state space, but it might also be only a couple of iterations away. In any way, it serves as an attractor for the development of a CA.

Stephen Wolfram found the following relationship to dynamic systems:

• Class I-behavior:
CAs evolve to limit points, i.e. to a homogeneous state after a finite number of time steps (example: rule 4).

• Class II-behavior:
CAs evolve to limit cycles, i.e. to short period structures (example: rule 2).

• Class III-behavior:
CAs evolve to strange attractors, i.e. to aperiodic patterns (example: rule 22).

• Class IV-behavior
CAs exhibit very long transient lengths. They yield stable, periodic and propagating structures which can persist over arbitrary lengths of time. Final states with any cycle length are possible (this has no direct analogue in the field of dynamic systems) (example: rule 110)

However, exact behavior may depend on the (here randomly generated) initial states of the CA.

Interesting patterns (classified class III or class IV) are neither ordered in a simply way, nor completely random. They are something between order and randomness (sometimes classified as BOAR).

Rules differ in their sensitivity to perturbations. “Simple” rules do not propagate perturbations, or propagate only sparsely. More interesting rules (= higher class rules) propagate more strongly.

Wolfram, Stephen (1983). Statistical Mechanics of Cellular Automata. Reviews of Modern Physics 55 (3): 601–644.

Wolfram, Stephen (2002). A New Kind of Science. Wolfram Media.