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.