Notes

Chapter 11: The Notion of Computation

Section 6: Emulating Cellular Automata with Other Systems


Cyclic tag systems [emulating tag systems]

From a tag system which depends only on its first element, with rules given as in the note below, the following constructs a cyclic tag system emulating it:

TS1ToCT[{n_, subs_}] := With[{k = Length[subs]}, Join[Map[v[Last[#], k] &, subs], Table[{}, {k(n - 1)}]]]

u[i_, k_] := Table[If[j i + 1, 1, 0], {j, k}]

v[list_, k_] := Flatten[Map[u[#, k] &, list]]

The initial condition for the tag system can be converted using v[list, k]. The list representing the complete history of the resulting cyclic tag system can then be interpreted using

Map[Map[Position[#, 1]1, 1 - 1 &, Partition[#, k]] &, Take[history, {1, -1, n k}]]

This construction is relevant to the proof of the universality of rule 110 starting on page 678.

From Stephen Wolfram: A New Kind of Science [citation]