TOPICS
Search

Rule 110


ElementaryCARule110

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 110=01101110_2. 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).

Rule 110 after 250 iterations

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 n cells in step n 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 2^n, 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).


See also

Elementary Cellular Automaton, Rule 30, Rule 50, Rule 54, Rule 60, Rule 62, Rule 90, Rule 94, Rule 102, Rule 126, Rule 150, Rule 158, Rule 182, Rule 188, Rule 190, Rule 220, Rule 222, Universal Cellular Automaton, Universality

Related Wolfram sites

http://atlas.wolfram.com/01/01/110/

Explore with Wolfram|Alpha

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.

Referenced on Wolfram|Alpha

Rule 110

Cite this as:

Weisstein, Eric W. "Rule 110." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Rule110.html

Subject classifications