Notes

Chapter 11: The Notion of Computation

Section 5: Emulating Other Systems with 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.