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]