Minsky Register Machine

A Minsky Register Machine (MRM) comprises a finite number of registers, a finite state automaton (FSA) embodying the instructions, and an initial state.

The registers are conventionally numbered 0 to n-1, but of course can also be given symbolic names.  Each register stores a nonnegative integer of unbounded magnitude.  Initial parameters for the computation are stored in some of the registers (conventionally registers 0 to k-1 for k parameters, all other registers usually set to zero).  When (and if) the machine halts, the result of the computation is found in some of the registers (conventionally in register 0).

The FSA comprises a finite number of states each of which represents an instruction.

There are three kinds of instruction (state): INC, DEC and HALT. A fourth instruction, NOP, is necessary for the operation of some Life MRM patterns, but any NOP instruction can be removed from the formal description of the underlying MRM without altering its function.

An INC instruction increments the value stored in one of the registers.  It has one possible next state, labelled pass.

A DEC instruction examines the contents of one of the registers.  If the register is nonzero, it is decremented and the next state is that corresponding to the nonzero condition, labelled pass.  If the register is zero, it is left unchanged and the next state is that corresponding to the zero condition, labelled fail.

A HALT instruction causes the machine to enter the halt state.  No further instructions are executed.  A HALT instruction has no next state.

An MRM can be specified using a symbolic-assembler-like language.  Here is such a specification for an MRM which adds the contents of Register 1 to Register 0:

        loop:   dec reg1 else goto exit
                inc reg0 and goto loop
        exit:   halt

This would be compiled into an FSA which in tabular form looks like this:
 
      State Type Reg Pass Fail
    ->   S0    DEC    1    S1    S2  
       S1 INC  0  S0  -
       S2 HALT  -  -  -

The arrow marks the initial state.


Universal Register Machine

A Universal Register Machine (URM) is an MRM capable of performing a computation of any MRM by emulation.

The complete specification of the MRM to be emulated (VMRM), and the initial values for the registers of the emulated computation to be performed, are encoded as the initial values for some of the URM's registers.  The conventional approach is to use Gödel numbers, ie products of prime powers.

A sparsely commented file containing the symbolic source program for the URM used in the Life Universal Computer described on these pages can be found here.

The VMRM specification and initial register contents are encoded as the initial values of six registers of the Life URM.  The first five registers contain Gödel numbers; informally:

And finally: The VMRM's s instructions (states) are assigned unique indices from 0 to s-1.  Let instruction i be represented by the ordered quadruple T[i] = (A[i], B[i], C[i], D[i]), where Let the VMRM's registers be numbered 0 to n-1.  Let R[j] be the initial value of the VMRM's register number j.
Let m be the index of the first instruction to be executed.
Let S denote some finite sequence S of n nonnegative integers S[i].
Let P(i) be the ith prime, where P(0) = 2.
For any sequence S, let Q[i](S) = P(S[i])-2.
For any sequence S, let G(S), the Gödel number of S, be the product of the terms P(i)^S[i] for all i.

Then the initial values of the URM's registers are:

Notes: Owing to the Unique Prime Factorization Theorem, any sequence of n nonnegative integers Z is uniquely represented by G(Z).  Thus given any j, R[j] can be extracted, and given any i, A[i], B[i], C[i] and D[i] can be extracted.  Prime-power extraction is performed in practice by the URM by repeated division until a nonzero remainder is produced.  The number of exact divisions is the prime power.

Here is an outline of the URM algorithm:


Virtual MRM Construction Example
 
      State Type Reg Pass Fail
    ->   S0    DEC    1    S1    S2  
       S1 INC  0  S0  -
       S2 HALT  -  -  -

Let VMRM registers 0 and 1 initially both contain 1.

R = (1, 1)

T[0] = (2, 1, 1, 2)
T[1] = (1, 0, 0, 0)
T[2] = (0, 0, 0, 0)

A = (2, 1, 0)
B = (1, 0, 0), Q(B) = (1, 0, 0)
C = (1, 0, 0), Q(C) = (1, 0, 0)
D = (2, 0, 0), Q(D) = (3, 0, 0)

registers = 2^1 . 3^1 = 6
opcodes =  2^2 . 3^1 . 5^0 = 12
operands = 2^1 . 3^0 . 5^0 = 2
passaddresses = 2^1 . 3^0 . 5^0 = 2
failaddresses = 2^3 . 3^0 . 5^0 = 8
base = P(0) = 2