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]