Notes

Chapter 11: The Notion of Computation

Section 5: Emulating Other Systems with Cellular Automata


Sequential substitution systems [from cellular automata]

Given a sequential substitution system with rules in the form used on page 893, the rules for a cellular automaton which emulates it can be obtained from

SSSToCA[rules_] := Flatten[{{v[_, _, _], u, _} -> u, {_, v[rn_, x_, _], u} -> r[rn + 1, x], {_, v[_, x_, _], _} -> x, MapIndexed[With[{rn = #2[[1]], rs = #1[[1]], rr = #1[[2]]}, {If[Length[rs] == 1, {u, r[rn, First[rs]], _} -> q[0, rr], {u, r[rn, First[rs]], _} -> v[rn, First[rs], Take[rs, 1]]], {u, r[rn, x_], _} -> v[rn, x, {}], {v[rn, _, Drop[rs, -1]], Last[rs], _} -> q[Length[rs] - 1, rr], Table[{v[rn, _, Flatten[{___, Take[rs, i - 1]}]], rs[[i]], _} -> v[rn, rs[[i]], Take[rs, i]], {i, Length[rs] - 1, 1, -1}], {v[rn, _, _], y_, _} -> v[rn, y, {}]}] & , rules /. s -> List], {_, q[0, {x__, _}], _} -> q[0, {x}], {_, q[0, {x_}], _} -> r[1, x], {_, q[0, {}], x_} -> r[1, x], {_, q[_, {___, x_}], _} -> x, {_, q[_, {}], x_} -> x, {_, x_, q[0, _]} -> x, {_, _, q[n_, {}]} -> q[n - 1, {}], {_, _, q[n_, {x___, _}]} -> q[n - 1, {x}], {q[_, {}], _, _} -> w, {q[0, {__, x_}], p[y_, _], _} -> p[x, y], {q[0, {__, x_}], y_, _} -> p[x, y], {p[_, x_], p[y_, _], _} -> p[x, y], {p[_, x_], u, _} -> x, {p[_, x_], y_, _} -> p[x, y], {_, p[x_, _], _} -> x, {w, u, _} -> u, {w, x_, _} -> w, {_, w, x_} -> x, {_, r[rn_, x_], _} -> x, {_, u, r[_, _]} -> u, {_, x_, r[rn_, _]} -> r[rn, x], {_, x_, _} -> x}]

The initial condition is obtained by applying the rule s[x_, y__] -> {r[1, x], y} and then padding with u's.

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