The rule 110 cellular automaton is a one-dimensional two-state cellular automaton with the following rule table:

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.

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.

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.

An example run of a rule 110 cellular automaton

Explanation of Universality Proof