Tag systems [emulating cellular automata]

Given the rules for an elementary cellular automaton in the form used on page 867, the following will construct a tag system which emulates it:

CAToTS[rules_] := {2, {{s[x_], s[y_]}  {d[x, y], d[x, y]}, {d[w_, x_], d[y_, z_]}  {s[{w, x, y} /. rules], s[{x, y, z} /. rules]}, {s[x_], d[y_, z_]}  {s[0], s[0], s[{0, y, z} /. rules]}, {d[x_, y_], s[z_]}  {s[{x, y, 0} /. rules], s[0], s[0]}}}

The initial condition for the tag system that corresponds to a single black cell in the cellular automaton is {s[0], s[0], s[1], s[0], s[0]}. Given a list of all steps in the evolution of the tag system, Cases[list, {__s}] picks out successive steps in the cellular automaton evolution.