Notes

Chapter 11: The Notion of Computation

Section 5: Emulating Other Systems with Cellular Automata


Substitution systems [from cellular automata]

Given a substitution system with rules in the form such as {1 {0}, 0 {0, 1}} used on page 889, the rules for a cellular automaton which emulates it are obtained from

SSToCA[rules_] := {{b, b, p[x_, _]} s[x], {_, s[v : (0 | 1)], p[x_, _]} p[v, x], {_, p[_, y_], _} s[y], {_, s[v : (0 | 1)], _m} m[v], {s[0 | 1], m[v : (0 | 1)], _} s[v], {b, m[v : (0 | 1)], _} r[v], {_, r[v : (0 | 1)], _} (Replace[v, rules] /. {{x_} s[x], {x_, y_} p[x, y]}), {_r, s[v : (0 | 1)], _} r[v], {_r, b, _} m[b], {s[0 | 1], m[b], _} b, {_, v_, _} v}

where specific values for cells can be obtained from

{b 0, s[0] 1, m[0] 2, p[0, 0] 3, r[0] 4, p[0, 1] 5, p[1, 0] 6, r[1] 7, p[1, 1] 8, m[1] 9, m[b] 10, s[1] 11}

An initial condition consisting of a single element with color i in the substitution system is represented by m[i] surrounded by b's in the cellular automaton. The specific definition given above works for neighbor-independent substitution systems whose elements have two possible colors, and in which each element is replaced at each step by at most two new elements.



Image Source Notebooks:

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