Implementation [of tag systems]

With the rules for case (a) on page 94 given for example by

{2, {{0, 0} {1, 1}, {1, 0} {}, {0, 1} {1, 0}, {1, 1} {0, 0, 0}}}

the evolution of a tag system can be obtained from

TSEvolveList[{n_, rule_}, init_, t_] := NestList[If[Length[#] < n, {}, Join[Drop[#, n], Take[#, n] /. rule]]&, init, t]

An alternative implementation is based on applying to the list at each step rules such as

{{0, 0, s___} {s, 1, 1}, {1, 0, s___} {s}, {0, 1, s___} {s, 1, 0}, {1, 1, s___} {s, 0, 0, 0}}

There are a total of ((k^{r + 1} - 1)/(k - 1))^{kn} possible rules if blocks up to length r can be added at each step and k colors are allowed. For r = 3, k = 2 and n = 2 this is 50,625.