Rule 110

Rule 110 is one of the elementary cellular automaton rules introduced by Stephen Wolfram in 1983 (Wolfram 1983, 2002). It specifies the next color in a cell, depending on its color and its immediate neighbors. Its rule outcomes are encoded in the binary representation . This rule is illustrated above together with the evolution of a single black cell it produces after 15 steps (OEIS A075437; Wolfram 2002, p. 55).

250 iterations of rule 110 are illustrated above.

The mirror image is rule 124, the complement is rule 137, and the mirrored complement is rule 193.

Starting with a single black cell, successive generations are given by interpreting the numbers 1, 6, 28, 104, 496, 1568, 7360, 27520, ... (OEIS A117999) in binary. Omitting trailing zeros (since the right  cells in step  of the triangle are always 0) gives the sequence 1, 3, 7, 13, 31, 49, 115, 215, 509, 775, 1805, ... (OEIS A006978), which are simply the previous numbers divided by , and the corresponding sequence is 1, 11, 111, 1101, 11111, ... (OEIS A070887).

Amazingly, the rule 110 cellular automaton is universal, as first conjectured by Wolfram (1986, pp. 485-557) and subsequently proven by Stephen Wolfram and his assistant Matthew Cook. This important discovery followed a program begun by Wolfram in 1985 to establish universality of rule 110. The main elements of the proof were put in place in 1994, with additional details and corrections continuing for several years (Wolfram 2002, p. 1115; Cook 2004).

The evolution of the rule 110 automaton for a specific initial condition is depicted on the cover of Wolfram (2002), as described in Wolfram (2002, p. 851).

REFERENCES:

Cook, M. "Universality in Elementary Cellular Automata." Complex Systems 15, 1-40, 2004.

McIntosh, H. V. "Rule 110 as It Relates to the Presence of Gliders." May 14, 2001. http://delta.cs.cinvestav.mx/~mcintosh/comun/abstracts/abstractrule110.html.

Sloane, N. J. A. Sequences A006978/M006978, A070887, A075437, and A117999 in "The On-Line Encyclopedia of Integer Sequences."

Wolfram, S. "Statistical Mechanics of Cellular Automata." Rev. Mod. Phys. 55, 601-644, 1983.

Wolfram, S. Theory and Application of Cellular Automata. World Scientific, 1986.

Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, pp. 32-38, 52, 675-691, 851, and 1115-1116, 2002.