Implementation [of register machines]

The state of a register machine at a particular step can be represented by the pair {n, list}, where n gives the position in the program of current instruction being executed (the "program counter") and list gives the values of the registers. The program for the register machine on page 99 can then be given as

{i[1], d[2, 1], i[2], d[1, 3], d[2, 1]}

where i[_] represents an increment instruction, and d[_, _] a decrement jump.

With this setup, the evolution of any register machine can be implemented using the functions (a typical initial condition is {1, {0, 0}})

RMStep[prog_, {n_Integer, list_List}] := If[n > Length[prog], {n, list}, RMExecute[prog〚n〛, {n, list}]]

RMExecute[i[r_], {n_, list_}] := {n + 1, MapAt[(# + 1)&, list, r]}

RMExecute[d[r_, m_], {n_, list_}] := If[list〚r〛 > 0, {m, MapAt[(# - 1)&, list, r]}, {n + 1, list}]

RMEvolveList[prog_, init:{_Integer, _List}, t_Integer] := NestList[RMStep[prog, #]&, init, t]

The total number of possible programs of length n using k registers is (k (1 + n))ⁿ. Note that by prepending suitable i[r] instructions one can effectively set up initial conditions with arbitrary values in registers.