Chapter 11: The Notion of Computation

Section 8: The Rule 110 Cellular Automaton

Tag systems [for rule 110]

The discussion in the main text and the construction above require a cyclic tag system with blocks that are a multiple of 6 long, and in which at least one block is added at some point in each complete cycle. By inserting k=6*Ceiling[Length[subs]/6] in the definition of TS1ToCT from page 1113 one can construct a cyclic tag system of this kind to emulate any one-element-dependence tag system.

From Stephen Wolfram: A New Kind of Science [citation]