Rule 110

In an elementary cellular automaton, a one-dimensional pattern of 0s and 1s evolves according to a simple set of rules.

In 2004, Matthew Cook published a proof that Rule 110 with a particular repeating background pattern is Turing complete, i.e., capable of universal computation, which Stephen Wolfram had conjectured in 1985.

[2] Cook presented his proof at the Santa Fe Institute conference CA98 before publication of Wolfram's book A New Kind of Science.

The final stage has exponential time overhead because the Turing machine's tape is encoded with a unary numeral system.

Neary and Woods (2006) presented a different construction that replaces 2-tag systems with clockwise Turing machines and has polynomial overhead.

[7] Matthew Cook presented his proof of the universality of Rule 110 at a Santa Fe Institute conference, held before the publication of A New Kind of Science.

Interest in his proof stemmed not so much from its result as from its methods, specifically from the technical details of its construction.

[8] The character of Cook's proof differs considerably from the discussion of Rule 110 in A New Kind of Science.

The data string in the cyclic tag system is represented by a series of stationary repeating structures of the type shown above.

Entering from the right are a series of left-moving structures of the type shown above, separated by varying amounts of horizontal space.

Large numbers of these structures are combined with different spacings to represent 0s and 1s in the cyclic tag system's production rules.

These structures are then made to append themselves to the end of the cyclic tag system's data string.