[Universal] register machines

The results of page 100 suggest that with 2 registers and up to 8 instructions no universal register machines (URMs) exist. Using the method of page 672 one can construct a URM with 3 registers and 175 instructions (or 2 registers and 4694 instructions) that emulates the universal Turing machine on page 706. Using work by Ivan Korec from the 1980s and 1990s one can also construct URMs which directly emulate other register machines. An example with 8 registers and 41 instructions is:

or

{d[4, 40], i[5], d[3, 9], i[3], d[7, 4], d[5, 14], i[6], d[3, 3], i[7], d[6, 2], i[6], d[5, 11], d[6, 3], d[4, 35], d[6, 15], i[4], d[8, 16], d[5, 21], i[1], d[3, 1], d[5, 25], i[2], d[3, 1], i[6], d[5, 32], d[1, 28], d[3, 1], d[4, 28], i[4], d[6, 29], d[3, 1], d[5, 24], d[2, 28], d[3, 1], i[8], i[6], d[5, 36], i[6], d[3, 3], d[6, 40], d[4, 3]}

Given any register machine, one first applies the function RMToRM2 from page 1114, then takes the resulting program and initial condition and finds an initial condition for the URM using

R2ToURM[prog_, init_] := Join[init, With[{n = Length[prog]}, {1 + LE[Reverse[prog] /. {i[x_]  x, d[x_, y_]  4 + 2 n + x - 2y}], n + 1, 0, 0, 0, 0}]]

For the first example on page 98 this gives {0, 0, 1471, 3, 0, 0, 0, 0}. The process of emulation is quite slow, with each emulated step in this example taking about 20 million URM steps.