Igblan - Minsky Regsiter Machine

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:

registers: The contents of the VMRM's registers.
opcodes: The VMRM's instructions.
operands: The register operands of the instructions.
passaddresses: The next instruction if this instruction passes.
failaddresses: The next instruction if this instruction fails.

And finally:

base: The VMRM's first instruction.

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

A[i] = 0 if the instruction is a HALT, 1 if it is an INC, and 2 if it is a DEC.
B[i] = The instruction's register number, or 0 if it is a HALT.
C[i] = The index of the next instruction to be executed if this instruction passes, or 0 if it is a HALT.
D[i] = The index of the next instruction to be executed if this instruction fails, or 0 if it is a HALT or an INC.

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:

registers: G(R)
opcodes: G(A)
operands: G(Q(B))
passaddresses: G(Q(C))
failaddresses: G(Q(D))
base: P(m)

Notes:

Q(B), Q(C) and Q(D) could be replaced with B, C and D, and the B[i]th, etc, prime calculated by the URM. This would produce smaller Gödel numbers, but make the URM larger.
Q(B), Q(C) and Q(D) could be replaced with P(B), P(C) and P(D). This would save 4 instructions in the URM, but would make the Gödel numbers larger.
The indices were specified the way they were as a compomise between making the Life URM as small as possible and making attainable the completion of a very small VMRM program running in emulation.

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:

Using base as the address of the current instruction, extract the operation from opcodes.
If the operation is HALT:

Halt.

Extract the register number from operands.
If the operation is DEC:

Attempt to divide registers exactly by the prime number representing the register number.
If the division failed:

Extract the address from failaddresses and store it in base.
Repeat from the beginning.

If the operation is INC:

Multiply registers by the prime number representing the register number.

Extract the address from passaddresses and store it in base.
Repeat from the beginning.

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