Elementary Cellular Automaton

The simplest class of one-dimensional cellular automata. Elementary cellular automata have two possible values for each cell (0 or 1), and rules that depend only on nearest neighbor values. 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 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 with an 8-bit binary number (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 illustrated 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 pattern 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). In fact, this rule is used as the random number generator used for large integers in the Wolfram Language (Wolfram 2002, p. 317).

The complete set of 256 (rules 0-255) elementary cellular automata are 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 can be written explicitly in terms of the adjacent cells from the previous generation as a trivariate function

(1)

If the values are represented by Boolean values, then the 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 fundamentally inequivalent rules (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.