Arithmetic systems [emulating register machines]

Given the program for a register machine with nr registers in the form on page 896, an arithmetic system which emulates it can be obtained from

RMToAS[prog_, nr_] := With[{p = Length[prog], g = Product[Prime[j], {j, nr}]}, {p g, Sort[Flatten[MapIndexed[With[{n = First[#2] - 1}, #1 /. {i[r_]  Table[n + j p  (1 + n Prime[r] (-n + #) &), {j, 0, g - 1}], d[r_, k_]  Table[n + j p  If[Mod[j, Prime[r]]  0, -1 + k + (-n + #)/Prime[r] &, # + 1 &], {j, 0, g - 1}]}] &, prog]]]}]

The rules for the arithmetic system are represented so that the system from page 122 becomes for example {2, {0  (3 #/2 &), 1 (3 (# + 1)/2 &)}}. If the register machine starts at instruction n with values regs in its registers, then the corresponding arithmetic system starts with the number n + Table[Prime[i]^reg〚i〛, {i, nr}] p - 1 where p = Length[prog]. The evolution of the arithmetic system is given by

ASEvolveList[{n_, rules_}, init_, t_] := NestList[(Mod[#, n] /. rules)[#] &, init, t]

Given a value m obtained in the evolution of the arithmetic system, the state of the register machine to which it corresponds is

{Mod[m, p] + 1, Map[Last, FactorInteger[Product[Prime[i], {i, nr}] Quotient[m, p]]] - 1}

Note that it is possible to have each successive step involve only multiplication, with no addition, at the cost of using considerably larger numbers overall.