Notes

Chapter 11: The Notion of Computation

Section 6: Emulating Cellular Automata with Other Systems


One-element-dependence tag systems [emulating TMs]

Writing the rule {3, {{0,_,_}->{0,0}, {1,_,_}->{1,1,0,1}}} from page 895 as {3,{0->{0,0},1->{1,1,0,1}}} the evolution of a tag system that depends only on its first element is obtained from

TS1EvolveList[rule_,init_,t_]:=NestList[TS1Step[rule,#]&,init,t] TS1Step[{n_,subs_},{}]={} TS1Step[{n_, subs_}, list_] := Drop[Join[list,First[list] /. subs], n]

Given a Turing machine in the form used on page 888 the following will construct a tag system that emulates it:

TMToTS1[rules_]:={2, Union[Flatten[rules /. ({i_, u_} -> {j_, v_, r_}) :> {(#[i] -> {#[i, 1], #[i, 0]}) & /@ {a,b, c, d}, If[r == 1, {a[i, u] -> {a[j], a[j]}, b[i, u] -> Table[b[j], {4}], c[i, u] -> Flatten[{Table[b[j], {2v}], Table[c[j], {2 - u}]}], d[i, u] -> {d[j]}}, {a[i, u] -> Table[a[j], {2 - u}], b[i, u] -> {b[j]}, c[i, u] -> Flatten[{c[j], c[j], Table[d[j], {2v}]}], d[i, u] -> Table[d[j], {4}]}]}]]}

A Turing machine in state i with a blank tape corresponds to initial condition {a[i], a[i], c[i]} for the tag system. The configuration of the tape on each side of the head in the Turing machine evolution can be obtained from the tag system evolution using

Cases[history, x : {a[_], ___} :> Apply[{#1, Reverse[#2]} &, Map[Drop[IntegerDigits[Count[x, #], 2], -1] &, {_b, _d}]]]

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