Elementary Cellular Automaton

An elementary cellular automaton is a one-dimensional cellular automaton with two possible values for each cell (0 or 1), whose rule depends only on the cell and its two nearest neighbors. As a result, the evolution of an elementary cellular automaton can completely be described by a table specifying the state a given cell will have in the next generation based on the value of the cell to its left, the value of the cell itself, and the value of the cell to its right. Since there are possible binary states for the three cells neighboring a given cell, there are a total of elementary cellular automata, each of which can be indexed by an 8-bit number in binary notation (Wolfram 1983, 2002). For example, the table giving the evolution of rule 30 () is illustrated above. In this diagram, the possible values of the three neighboring cells are shown in the top row of each panel, and the resulting value the central cell takes in the next generation is shown below in the center. generations of elementary cellular automaton rule are implemented as CellularAutomaton[r, 1, 0, n].

The evolution of a one-dimensional cellular automaton can be illustrated by starting with the initial state (generation zero) in the first row, the first generation on the second row, and so on. For example, the figure above illustrates the first 20 generations of the rule 30 elementary cellular automaton starting with a single black cell.

The illustrations above show some automata numbers that give particularly interesting patterns propagated for 15 generations starting with a single black cell in the initial iteration. Rule 30 is of special interest because it is chaotic (Wolfram 2002, p. 871), with central column given by 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, ... (OEIS A051023). This rule was used for generating random numbers in the Mathematica versions described by Wolfram (2002, p. 317).

The complete set of 256 elementary cellular automata (rules 0-255) is illustrated below for a starting condition consisting of a single black cell.

Letting denote the state of the th cell (for running from to ) at time , 1, ..., its value for can be written explicitly in terms of the adjacent cells from the previous generation as a trivariate function

(1)

If the states are represented by Boolean variables, then the Boolean functions may have particularly simple forms for certain rules. In particular,

			(2)
			(3)
			(4)
			(5)
			(6)

(Wolfram 2002, p. 869).

Of the elementary cellular automata, there are 88 inequivalent rules under left-right reflection and interchange of the cell values 0 and 1 (Wolfram 2002, p. 57).

The amphichiral elementary cellular automata are 0, 1, 4, 5, 18, 19, 22, 23, 32, 33, 36, 37, 50, 51, 54, 55, 72, 73, 76, 77, 90, 91, 94, 95, 104, 105, 108, 109, 122, 123, 126, 127, 128, 129, 132, 133, 146, 147, 150, 151, 160, 161, 164, 165, 178, 179, 182, 183, 200, 201, 204, 205, 218, 219, 222, 223, 232, 233, 236, 237, 250, 251, 254, and 255.