Minsky Register Machine |
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.
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:
Then the initial values of the URM's registers are:
Here is an outline of the URM algorithm:
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