Cyclic tag systems which allow any value for each element can be obtained by adding the rule CTStep[{{r_, s___}, {n_, a___}}] := {{s, r}, Flatten[{a, Table[r, {n}]}]} The leading elements in this case can be obtained using CTListStep[{rules_, list_}] := {RotateLeft[rules, Length[list]], With[{n = Length[rules]}, Flatten[Apply[Table[#1, {#2}] &, Map[Transpose[ {rules, #}] &, Partition[list, n, n, 1, 0]], {2}]]]}

Every cycle corresponds in effect to a distinct necklace with n beads; with k colors the total number of these is Apply[Plus, (EulerPhi[n/#] k # &)[Divisors[n]]]/n The number of cycles of length exactly m is s[m, k]/m , where s[m, k] is defined on page 950 .

Note that the evolution of such systems is also analogous to the process of applying transfer matrices in studies of spin systems like Ising models.)

Indeed, even after a million steps, when the Results of applying the rule n  If[EvenQ[n], 5n/2, (n + 1)/2] , starting with different initial choices of n .

Starting with a single state consisting of one element, the picture then shows that applying these rules immediately gives two possible states: one with a single element, and the other with two.

The picture shows what happens when one starts with just one black cell and then applies this rule over and over again.

What about other schemes for applying replacements?

Any consistent choice of such slices will correspond to a possible evolution history—with the same underlying rules, but potentially a different scheme for determining the order in which to apply replacements.

The pictures below show what happens if one takes various patterns, arranges their rows one after another in a long line, and then applies pointer-based encoding to the resulting sequences.

And as the pictures on the next page illustrate, it turns out that just repeatedly applying the combinator expression below reproduces successive steps in the evolution of rule 110.