TOPICS
Search

Elementary Cellular Automaton


ElementaryCA30Rules

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 2×2×2=2^3=8 possible binary states for the three cells neighboring a given cell, there are a total of 2^8=256 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 (30=00011110_2) 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. n generations of elementary cellular automaton rule r are implemented as CellularAutomaton[r, {{1}, 0}, n].

ElementaryCA30

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.

ElementaryCARulesElementaryCA

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.

ElementaryCA1ElementaryCA2ElementaryCA3ElementaryCA4ElementaryCA5

Letting a_i(t) denote the state of the ith cell (for i running from -infty to infty) at time t=0, 1, ..., its value can be written explicitly in terms of the adjacent cells from the previous generation as a trivariate function

 a_i(t)=f(a_(i-1)(t-1),a_i(t-1),a_(i+1)(t-1)).
(1)

If the values a_i(t) are represented by Boolean values, then the functions may have particularly simple forms for certain rules. In particular,

f_(30)(p,q,r)=Xor[p,Or[q,r]]
(2)
f_(90)(p,q,r)=Xor[p,r]
(3)
f_(110)(p,q,r)=Xor[Or[p,q],And[p,q,r]]
(4)
f_(250)(p,q,r)=Or[p,r]
(5)
f_(254)(p,q,r)=Or[p,q,r]
(6)

(Wolfram 2002, p. 869).

Of the 2^8=256 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.


See also

Cellular Automaton, Rule 30, Rule 54, Rule 60, Rule 62, Rule 90, Rule 94, Rule 102, Rule 110, Rule 126, Rule 150, Rule 158, Rule 182, Rule 188, Rule 190, Rule 220, Rule 222, Totalistic Cellular Automaton

Explore with Wolfram|Alpha

References

Rangel-Mondragon, J. "A Catalog of Cellular Automata." http://library.wolfram.com/infocenter/MathSource/505/.Sloane, N. J. A. Sequence A051023 in "The On-Line Encyclopedia of Integer Sequences."Wolfram, S. "Statistical Mechanics of Cellular Automata." Rev. Mod. Phys. 55, 601-644, 1983.Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, pp. 23-60, 112, and 865-866, 2002.

Referenced on Wolfram|Alpha

Elementary Cellular Automaton

Cite this as:

Weisstein, Eric W. "Elementary Cellular Automaton." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/ElementaryCellularAutomaton.html

Subject classifications