Chapter 3: The World of Simple Programs

Section 8: Cyclic Tag Systems

History [of cyclic tag systems]

Cyclic tag systems were studied by Matthew Cook in 1994 in connection with working on the rule 110 cellular automaton for this book. The sequence {1,2,2,1,1,2,…} defined by the property list==Map[Length,Split[list]] was suggested as a mathematical puzzle by William Kolakoski in 1965 and is equivalent to

Join[{1,2}, Map[First, CTEvolveList[{{1},{2}}, {2}, t]]]

It is known that this sequence does not repeat, contains no more than two identical consecutive blocks, and has at least very close to equal numbers of 1's and 2's. Replacing 2 by 3 yields a sequence which has a fairly simple nested form.

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