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.