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.

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