Cellular Automata

The term cellular automaton can refer to many different systems of cells that evolve according to deterministic local rules. The cellular automata we're working with here are second-order elementary automata. The rules are as follows:

The automaton lives on a grid described by a function A(x,t) ∈ {0,1} for integers x and t, representing space and time. x is finite with periodic boundary conditions, but t is unlimited. In this demo, x is the horizontal coordinate and t is the vertical coordinate. If A(x,t) = 0, that cell of the grid will be colored white; if A(x,t) = 1, that cell will be colored black.

We can compute each cell from the two rows above it as follows: the cell's value is the XOR of the cell two rows above it, and some function of the three nearest cells in the row directly above it. The function is called the rule. More formally, A(x,t+1) = F[A(x-1,t), A(x,t), A(x+1,t)] ⊕ A(x,t-1). The rule F : {0,1}3 → {0,1} can be anything. There are 256 possibilities; some rules produce interesting patterns and others are boring.

Different rules are associated with numbers from 0 to 255 by writing the function's values in order, then interpreting that as a binary number. These numbers are called Wolfram codes. Formally, F's Wolfram code is Σi,j,k∈{0,1} 24i+2j+k×F(i,j,k). Because the same numbering scheme is used for first-order elementary automata rules, we append an "R" to avoid confusion. So the second-order elementary automata rules are written as 0R, 1R, and so on up to 255R.

One very interesting property of second-order elementary automata is that they are always reversible; given A(x,t) for all values of x and any two adjacent values of t, we can compute all values of A(x,t).

Back to the demo