Notes

Chapter 11: The Notion of Computation

Section 6: Emulating Cellular Automata with Other Systems


Register machines with many registers [from 2 registers]

It turns out that a register machine with any number of registers can always be emulated by a register machine with just two registers. The basic idea is to encode the list of values of all the registers in the multiregister machine in the single number given by

RMEncode[list_] := Product[Prime[j]^list[[j]], {j, Length[list]}]

and then to have this number be the value at appropriate steps of the first register in the 2-register machine. The program in the multiregister machine can be converted to a program for the 2-register machine according to

RMToRM2[prog_] := Module[{segs, adrs}, segs = MapIndexed[seg, prog]; adrs = FoldList[Plus, 1, Map[Length, segs]]; MapIndexed[(# /. {ds[r_,s_] :> d[r, adrs[[s]]], dr[r_,j_] :> d[r, j + First[#2]]})&, Flatten[segs]]] seg[i[r_], {a_}] := With[{p = Prime[r]}, Flatten[{Table[i[2], {p}], dr[1, -p], i[1], dr[2, -1], Table[dr[1, 1], {p+1}]}]] seg[d[r_, n_], {a_}] := With[{p = Prime[r]}, Flatten[{i[2], dr[1, 5], i[1], dr[2, -1], dr[1, 1], ds[1, n], Table[{If[m==p-1, ds[1, a], dr[1,3p+2-m]], Table[i[1], {p}], dr[2, -p], Table[dr[1, 1], {2p-m-1}], ds[1, a+1]}, {m, p-1}]}]]

The initial conditions for the 2-register machine are given by {1, {RMEncode[list], 0}} and the results corresponding to each step in the evolution of the multiregister machine appear whenever register 2 in the 2-register machine is incremented from 0.

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