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[{r n = #21, rs = #11, rr = #12}, {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]}]], rsi, _} v[rn, rsi, 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.



Image Source Notebooks:

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