The rule 110 cellular automaton is a one-dimensional two-state cellular automaton with the following rule table: A cellular automaton (plural: cellular automata) is a discrete model studied in computability theory, mathematics, and theoretical biology. ...

Rule 110, like the Game of Life, exhibits what Stephen Wolfram calls "Class 4 behavior," which is neither completely random nor completely repetitive. Localized structures appear and interact in various complicated-looking ways. In the course of the development of A New Kind of Science, Wolfram's research assistant Matthew Cook proved that these structures were rich enough to support universal computation. This is an interesting result because Rule 110 is an extremely simple system, simple enough to suggest that naturally occurring physical systems may also be capable of universality—and hence questions about them will often be undecidable. This means they may not be amenable to closed-form mathematical solutions. Gosper Glider Gun creating gliders. The Game of Life is a cellular automaton devised by the British mathematician John Horton Conway in 1970. ... Stephen Wolfram (born August 29, 1959 in London) is a scientist known for his work in particle physics, cellular automata and computer algebra, and is the creator of the computer program Mathematica. ... A New Kind of Science is a controversial book by Stephen Wolfram, published in 2002. ... Matthew Cook was born in Morgantown, West Virginia, in 1970 and grew up in Evanston, Illinois. ... The Turing machine is an abstract machine introduced in 1936 by Alan Turing to give a mathematically precise definition of algorithm or mechanical procedure. As such it is still widely used in theoretical computer science, especially in complexity theory and the theory of computation. ...

Matthew Cook presented his proof before the publication of A New Kind of Science at a Santa Fe Institute conference, which Wolfram Research claimed was a violation of Cook's nondisclosure agreement. The proof was stripped from the proceedings by court order. Nevertheless the proof's existence became known. However, the interest it generated was primarily about the technical details of its construction, rather than the significance of its existence--and hence of a considerably different character from its treatment in the book NKS. The Santa Fe Institute [SFI] is A non-profit research institute in Santa Fe, New Mexico founded by Murray Gell-Mann in 1984 to study complex systems and disseminate the notion of a separate interdisciplinary study of complexity theory. ...

Since the publication of A New Kind of Science, Matthew Cook has prepared a paper giving the complete proof, now published in Complex Systems, Volume 15, Issue 1.

Smaller version of CA_rule110. ...

An example run of a rule 110 cellular automaton

Explanation of Universality Proof