# Notes

## 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_}) {Map[#[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]