Notes

Chapter 11: The Notion of Computation

Section 5: Emulating Other Systems with Cellular Automata


Register machines [from cellular automata]

Given the program for a register machine in the form used on page 896, the rules for a cellular automaton that emulates it can be obtained from

g[i[1], p_, m_] := {{_, p, _} p + 1, {_, 0, p} m + 2, {_, _, p} m + 3}

g[i[2], p_, m_] := {{_, p, _} p + 1, {p, 0, _} m + 5, {p, _, _} m + 6}

g[d[1, q_], p_, m_] := {{m + 2 | m + 3, p, _} q, {m + 1, p, _} p, {0, p, _} p + 1, {_, m + 2 | m + 3, p} m + 1}

g[d[2, q_], p_, m_] := {{_, p, m + 5 | m + 6} q, {_, p, m + 4} p, {_, p, 0} p + 1, {p, m + 5 | m + 6, _} m + 4}

RMToCA[prog_] := With[{m = Length[prog]}, Flatten[{MapIndexed[g[#1, First[#2], m] &, prog], {{0, 0 | m + 1, m + 3} m + 2, {0, m + 1, _} 0, {0, 0, m + 1} 0, {_, _, x : (m + 1 | m + 3)} x, {_, m + 1 | m + 3, _} m + 2, {m + 6, 0 | m + 4, 0} m + 5, {_, m + 4, 0} 0, {m + 4, 0, 0} 0, {x : (m + 4 | m + 6), _, _} x, {_, m + 4 | m + 6, _} m + 5, {_, x_ , _} x}}]]

If m is the length of the register machine program, then the resulting cellular automaton has m + 7 possible colors for each cell. If the initial numbers in the two registers are a and b, then the initial conditions for the cellular automaton are Join[Table[m + 2, {a}], {1}, Table[m + 5,{b}]] surrounded by 0's.

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