Gregušová-Korec universal Minsky machine

In 1979 Ľudmila Gregušová and Ivan Korec presented their design for a universal Minsky machine which uses 37 instructions, or 32 if the input to the emulated machine is encoded in a special way. The machine emulates a 3 counter Minsky machine, or 2 counter for the 32 instruction variant. Instructions are stored as remainders of the program modulo some prime. The structure of this article roughly matches their paper.

Overview

Like all universal machines, Gregušová and Korec's machine relies on an input program which is then used to carry out operations on input data. The authors use a clever method of encoding the input program as a very large integer which has a number of remainders modulo certain primes, with all other remainders for all other moduli being zero. This encoding permits the instruction fetcher to be very simple.

The machine itself simulates a 3-counter Minsky machine. The simulated machine's registers correspond exactly to 3 of the outer machine's registers, which simplifies operations involving them. Other methods are possible but require packing multiple counters into a single counter, which greatly complifies the process.

Marvin Minsky provided a proof on the universality of 2-counter machines. Gregušová and Korec state that such a machine requires exponential input. I.E. if a machine with more than 2 counters is Φ(x) then there exists a 2 counter machine which produces equivalent results with its input x being coded as p^x for some prime p, and output being similarly coded.

Outer machine

Gregušová and Korec utilize a variant of the Minsky machine. The machine has counters as normal, with the counters containing values from the set of non-negative integers, i.e. 0, 1, 2... Each counter is labeled S_i with i being a non-negative integer. Similarly, each state (corresponding to a line in most other implementations) is labeled as q_i with i also being a non-negative integer, q₀ being the halting state, and q₁ being the initial state. The machine's instructions are in one of 3 forms, presented as 4-tuples:

• (q_i, S_j, P, q_k): increment counter S_j and transition to q_k
• (q_i, S_j, M, q_k): decrement counter S_j and transition to q_k, decrementation never results in a negative number
• (q_i, S_j, q_m, q_n): test the contents of S_j, if they are non-zero transition to q_m, if they are zero transition to q_n

The first element of an instruction tuple is the state the instruction corresponds to. Each state corresponds to exactly one instruction, so no two instruction tuples may have the same first element in a given machine.

Gregušová and Korec utilize a notation Φ_Zⁿ(x₁, x₂, ..., x_n) which denotes the equivalent partial function computed by a machine Z on the inputs x₁, x₂, ..., x_n. If Z is a Minsky machine, computing Φ_Zⁿ(x₁, x₂, ..., x_n) is done by assigning S₁ = x₁, S₂ = x₂, ..., S_n = x_n, assigning all other counters to 0, then operating the machine. If the machine does not halt then the function is undefined. If it does halt, then the output of the function is in S₀.

Inner machine (M3)

The machine which is emulated inside of the outer machine is another variant of the standard Minsky machine. The inner machine only has 3 counters, each of which will correspond to one of the outer machine's counters. The machine is referred to as an M3-machine in the paper. This variant has 4 instruction forms, with the notation being otherwise the same:

• (q_i, P, q_j): increment all counters and transition to q_j
• (q_i, S_n, q_j): check if S_n is zero, decrement if so and transition to q_j, otherwise transition to q_j+1

With n being 0, 1, or 2.

Each instruction can be matched with an operation code (opcode), with the universal machine using (q_i, S₀, q_j) = 0, (q_i, S₁, q_j) = 1, (q_i, S₂, q_j) = 2, (q_i, P, q_j) = 3.

Three counter Minsky machines using instructions from the last section can be translated into an equivalent M3 machine. To assist translation, a no-op construction is used.

• no-op (q_i, q_j) = (q_i, P, q_i+1), (q_i+1, S₀, q_i+2), (q_i+2, S₁, q_i+3), (q_i+3, S₂, q_j)

Instruction	M3 instruction	Note
(qi, S0, P, qk)	(qi, P, qi+1), (qi+1, S1, qi+2), (qi+2, S2, qk)	Procedure is the same for S1 and S2 with the later subtractions changed accordingly
(qi, Sj, M, qk)	(qi, Sj, qi+1), (qi+1, qk), (qi+2, qk)	The indices of the first no-op's instructions after the initial P must be shifted after the second no-op
(qi, Sj, qm, qn)	(qi, Sj, qi+1), (qi+1, qp), (qi+2, qn), (qp, Sj, P, qm)	The indices of the first no-op must be shifted as before. The final P instruction recovers the value of Sj

Instruction encoding

If the instructions for a 3-counter machine were to be stored in a list, we could forego the first element which identifies what state the instruction corresponds to. We could immediately identify what instructions correspond to what states by simply indexing the list, as opposed to them being stored in an unordered set. If they were then to be stored as non-negative integers, we could use the opcodes to encode the actual action of the instruction. To encode the target of the jump the jump target number can be shifted up by 4, leaving a quaternary digit of space for the operation, then both can be added together. Encoded instructions are therefore in the fork 4j+k, with j being the jump target, and k being the opcode.

To pack an entire program into a single integer, an integer r must be found such that the rth prime number (denoted P_r, with P₀ = 2) is greater than 4v+3, with v being the maximal state in the program. 4v+3 represents the biggest possible instruction representable for a machine with v states. Note that this prime has the property any instruction for the given machine can be divided by it, with the remainder always being the instruction. An additional requirement is that P_r+v is less than 2*P_r. There are many primes which will satisfy these conditions for a given machine.

Gregušová and Korec then state that the encoded program y must satisfy the following congruences:

y ≡ 4j + k (mod P_r+w)

This congruence holds for all w, each w being a state number in the machine. E.G. if the machine has the instructions (q₁, P, q₂), (q₁, S₀, q₁), (q₁, S₁, q₀) then each instruction is encoded as 4*2+3 = 11, 4*1+0 = 4, 4*0+1 = 1, and the following congruences must hold: y ≡ 11 (mod P_r+1), y ≡ 4 (mod P_r+2), y ≡ 1 (mod P_r+3).

These congruences lay the groundwork for an interesting method of indexing instructions. If we have a list of primes starting at r, we can pick the primes in order from the list and index each instruction by taking the modulo of the program with that plucked prime. Once we take the modulo we can split the encoded instruction into its target state and operation.

If the machine has any states (numbered u) which do not correspond to an instruction, then the following congruences must also hold:

y ≡ 4u (mod P_r+u)

Finally, for all primes less than or equal to r, denoted P_k with k ≤ r, the following congruences must hold:

y ≡ 0 (mod P_kⁿ)

Such that P_kⁿ is the highest power of P_k which does not equal or exceed P_r+v, the property P_kⁿ < P_r+v < P_kⁿ⁺¹ holding for all k. n = ⌊log(P_r+v)/log(P_k)⌋

These congruences are solvable according to the Chinese remainder theorem. Altogether, the congruences mean that for any number less than P_r the remainder of the program y with that number will be zero, and after that only every prime will result in a remainder. A program encoded this way can be decoded by successively dividing it by every number. Each remainder corresponds to another encoded instruction, with the ith instruction being the ith non-zero remainder of y. A simple, albeit inefficient, algorithm can be used to fetch the ith instruction:

def fetch(program, i):
    divisor = 1
    while i:
       remainder = program % divisor
       if remainder != 0:
           i -= 1
    return remainder # instruction in the form 4j+k

The machine

Gregušová and Korec divide their machine into two major components, with an extra set of 3 states, those being the working unit, and decoder. However, it may be easier to understand the machine by separating it into four components; the fetch section, decoder, execution section, and halt detection. Additionally, their model starts at what is labeled in this diagram as q₁₉, the number of this state was swapped with q₁ to simplify the startup path.

The machine utilizes 8 registers, S₀ through S₇. The machine operates in accordance with the phi notation, with a function computed on the universal machine denoted as Φ_U²(y, x), y being the program which the universal machine executes. For any given Φ_Z¹(x) there is a y such that Φ_Z¹(x) = Φ_U²(y, x), meaning that for any program on a Turing-complete or lesser machine, there is a program y for the Gregušová-Korec machine which simulates it, which is the requirement for universality. This means that to compute Φ_U²(y, x) S₁ is set to y (the program), S₂ is set to x (the program's input), the machine is run, and if it halts, the output is read from S₀.

Each counter serves a specific function.

Counter	Purpose	Relation with other counters	Form
S0	emulated machine's output counter
S1	input program	y = S1 + S4	Prime modulo encoded list
S2	emulated machine register
S3	emulated machine register
S4	scratch register for dividing the program	y = S1 + S4
S5	instruction to execute	last divisor = S5 + S6	4j+k
S6	scratch register for dividing the program	last divisor = S5 + S6
S7	jump target of the last instruction		j

Execution

The execution section is easiest to understand. After the decoder is finished, S₅ will be examined and will issue a command on the emulated machine's registers. There are 4 sections of the execution component, corresponding to the four M3-machine commands. Recall that the decrement commands are conditional, when issued on a register that is zero, they cause a jump to j+1 instead of j. This is true for all of the decrement instructions, so the execution component shares the increment j (increment S₇) instruction between all of the decrement instructions. This state also serves a role in the initial machine startup, so it's part of the halt detection section.

Halt detection

Halt detection has two states, and two entry points. For unsuccessful decrements, as well as on machine state, the halt section is entered via the the S₇ decrement state. For all successful operations it is skipped. The increment serves two purposes. In the case of an unsuccessful decrement, it causes the emulated machine to jump to j+1 instead of j. When the machine first starts only S₁ and S₂ can be nonzero, meaning the jump target S₇ will be zero, as would the first instruction to operate S₅, so the machine needs to fetch the first instruction. In order to so S₇ must be 1 so that the fetch section can successful retrieve it. The dual-purpose S₇ increment performs this function, resulting in S₇ always being 1 on startup. The other state of the halt section checks S₇, halting the machine if it is zero, otherwise continuing to the fetch section.

Fetch

The fetch section retrieves the S₇th instruction from the program, stored in S₁. It implements the algorithm presented in the instruction encoding section. It first moves the contents of S₁ into S₄, by the end of this sections operations the contents will be moved back. It then increments S₅ and moves any contents from S₆ into S₅. It then begins a loop where it attempts to pair up each element from S₅ with an element from S₄ by subtracting one from each and adding one to their auxiliary registers. If S₅ is depleted, S₆ is emptied back into S₅, which refreshes it to its prior value as the contents were moved from S₅ to S₆ at each pairing. Eventually S₄ will completely empty into S₁, restoring the program. At this point the machine checks if S₅ is zero or not. If S₅ is zero, then each element of some multiple of S₅ could be successfully paired with an element of S₄, meaning that S₄ mod S₅ ≡ 0. If S₅ is not zero then there is a remainder from that division. If there was no remainder then the machine goes back near the start of the fetch section to move S₁ into S₄ and repeat with a new divisor. Since S₅ is incremented each loop, this has the effect of trying each divisor 1, 2, 3, etc. in turn. If S₅ was nonzero then S₇ (the jump target) is decremented. If S₇ is zero, meaning that j many remainders were found, then the machine proceeds to the decoder, otherwise it continues dividing. At the end of this section S₅ should be in the form 4j+k, corresponding to the instruction at position S₇.

Decoder

Finally, the decoder section serves to decode S₅ and issue the appropriate command on the emulated machine's counters. Assume that S₅ is in the form k. This means that S₅ is either 0, 1, 2, or 3, corresponding to an M3 instruction. The decoder checks if S₅ is zero, and if so it goes to the state which issues an S₀ decrement. If it is not zero, it decrements S₅ and checks if it is now zero. If it is, that corresponds to S₅ having been 1, so an S₂ decrement is issued. This process is repeated for the final two M3 instructions. Note that S₅ is 4j+k when this section is entered. The final two states of the decoder serve to decode 4j+k into j and k. Note how there are 4 S₅ decrement states. Say that S₅ is in the form 4j+k. After the first decrement, S₅ is 4j+k-1, after the second, 4j+k-2, then 4j+k-3, and finally 4j+k-4. Assuming j ≥ 1 at no point is S₅ k, so no command is issued during the loop. We can rearrange S₅'s new value as 4j + k - 4 → (j)4 + k + (-1)4 → (j-1)4 + k → 4(j-1) + k. Thus, after one round of the decoder, the j is decremented by one. Since S₇ is incremented each loop, S₇ = j after the loop continues until S₅ = k.