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.Gregušová, Ľ., Korec, I. (1979). Small universal Minsky machines. In: Bečvář, J. (eds) Mathematical Foundations of Computer Science 1979. MFCS 1979. Lecture Notes in Computer Science, vol 74. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-09526-8_28 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 px 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 Si with i being a non-negative integer. Similarly, each state (corresponding to a line in most other implementations) is labeled as qi with i also being a non-negative integer, q0 being the halting state, and q1 being the initial state. The machine's instructions are in one of 3 forms, presented as 4-tuples:
* (qi, Sj, P, qk): increment counter Sj and transition to qk
* (qi, Sj, M, qk): decrement counter Sj and transition to qk, decrementation never results in a negative number
* (qi, Sj, qm, qn): test the contents of Sj, if they are non-zero transition to qm, if they are zero transition to qn
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 ΦZn(x1, x2, ..., xn) which denotes the equivalent partial function computed by a machine Z on the inputs x1, x2, ..., xn. If Z is a Minsky machine, computing ΦZn(x1, x2, ..., xn) is done by assigning S1 = x1, S2 = x2, ..., Sn = xn, 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 S0.
== 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:
* (qi, P, qj): increment all counters and transition to qj
* (qi, Sn, qj): check if Sn is zero, decrement if so and transition to qj, otherwise transition to qj+1
With n being 0, 1, or 2.
Each instruction can be matched with an operation code (opcode), with the universal machine using (qi, S0, qj) = 0, (qi, S1, qj) = 1, (qi, S2, qj) = 2, (qi, P, qj) = 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 (qi, qj) = (qi, P, qi+1), (qi+1, S0, qi+2), (qi+2, S1, qi+3), (qi+3, S2, qj)
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 Pr, with P0 = 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 Pr+v is less than 2*Pr. 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 Pr+w)
This congruence holds for all w, each w being a state number in the machine. E.G. if the machine has the instructions (q1, P, q2), (q1, S0, q1), (q1, S1, q0) 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 Pr+1), y ≡ 4 (mod Pr+2), y ≡ 1 (mod Pr+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 Pr+u)
Finally, for all primes less than or equal to r, denoted Pk with k ≤ r, the following congruences must hold:
y ≡ 0 (mod Pkn)
Such that Pkn is the highest power of Pk which does not equal or exceed Pr+v, the property Pkn < Pr+v < Pkn+1 holding for all k. n = ⌊log(Pr+v)/log(Pk)⌋
These congruences are solvable according to the Chinese remainder theorem. Altogether, the congruences mean that for any number less than Pr 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 q19, the number of this state was swapped with q1 to simplify the startup path.
The machine utilizes 8 registers, S0 through S7. The machine operates in accordance with the phi notation, with a function computed on the universal machine denoted as ΦU2(y, x), y being the program which the universal machine executes. For any given ΦZ1(x) there is a y such that ΦZ1(x) = ΦU2(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 ΦU2(y, x) S1 is set to y (the program), S2 is set to x (the program's input), the machine is run, and if it halts, the output is read from S0.
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, S5 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 S7) 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 S7 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 S1 and S2 can be nonzero, meaning the jump target S7 will be zero, as would the first instruction to operate S5, so the machine needs to fetch the first instruction. In order to so S7 must be 1 so that the fetch section can successful retrieve it. The dual-purpose S7 increment performs this function, resulting in S7 always being 1 on startup. The other state of the halt section checks S7, halting the machine if it is zero, otherwise continuing to the fetch section.
=== Fetch ===
The fetch section retrieves the S7th instruction from the program, stored in S1. It implements the algorithm presented in the instruction encoding section. It first moves the contents of S1 into S4, by the end of this sections operations the contents will be moved back. It then increments S5 and moves any contents from S6 into S5. It then begins a loop where it attempts to pair up each element from S5 with an element from S4 by subtracting one from each and adding one to their auxiliary registers. If S5 is depleted, S6 is emptied back into S5, which refreshes it to its prior value as the contents were moved from S5 to S6 at each pairing. Eventually S4 will completely empty into S1, restoring the program. At this point the machine checks if S5 is zero or not. If S5 is zero, then each element of some multiple of S5 could be successfully paired with an element of S4, meaning that S4 mod S5 ≡ 0. If S5 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 S1 into S4 and repeat with a new divisor. Since S5 is incremented each loop, this has the effect of trying each divisor 1, 2, 3, etc. in turn. If S5 was nonzero then S7 (the jump target) is decremented. If S7 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 S5 should be in the form 4j+k, corresponding to the instruction at position S7.
=== Decoder ===
Finally, the decoder section serves to decode S5 and issue the appropriate command on the emulated machine's counters. Assume that S5 is in the form k. This means that S5 is either 0, 1, 2, or 3, corresponding to an M3 instruction. The decoder checks if S5 is zero, and if so it goes to the state which issues an S0 decrement. If it is not zero, it decrements S5 and checks if it is now zero. If it is, that corresponds to S5 having been 1, so an S2 decrement is issued. This process is repeated for the final two M3 instructions. Note that S5 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 S5 decrement states. Say that S5 is in the form 4j+k. After the first decrement, S5 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 S5 k, so no command is issued during the loop. We can rearrange S5'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 S7 is incremented each loop, S7 = j after the loop continues until S5 = k.
== References ==
Category:Languages Category:Before 1993