User:Salpynx/Minimal TC program machines
Table of minimal TC program / counter machines
Argument notation
- r: a specific register.
- z: a specific instruction branch (forwards or backwards). Absence of z implies implicit z + c, 'next' (by a constant) instruction transition.
Mnemonics
jzdec(r, z)means: Jump-if-zero, else decrement. Which reflects what happens and what order it happens in.dec(r, zTRUE, zFALSE)means: Attempt to decrement register. If decrement succeeds, jump tozTRUE, else jump tozFALSE
| ref # | Instruction set | Registers | Is minimal? | Name | Source |
|---|---|---|---|---|---|
{ clear(r), inc(r), jzdec(r, z), halt() } |
n | - | General Minsky Program machine (11.1) | Minsky, 1967, 11.1 (p.200) | |
{ inc(r), jzdec(r, z) } |
5 | F | Program for a Turing Machine | Minsky, 1967, 11.2 (p.204) | |
{ inc(r), jzdec(r, z), go(z) } |
4 | F | Program for a Turing Machine, with reg w≡0 used for unconditional branches replaced with a go(z) instruction | Minsky, 1967, 11.2 (p.204), using the go(z) construction from 11.1) | |
{ clear(r), incr(r), jzdec(r, z) } |
3 | F | 11.4 Simple Universal Base for a Program Counter (reducing registers) | Minsky, 1967, 11.4 (p.206) | |
{ inc(r), jzdec(r, z) } |
4 | F | 11.4 Simple Universal Base for a Program Counter (reducing instructions) | ||
{ inc(r), jdecnz(r, z) } |
4 | F | 11.4 Simple Universal Base for a Program Counter (reducing instructions, with alternate jump logic: jump NOT zero) | Minsky, 1967, 11.4 (p.207) | |
{ inc(r), jzdec(r, z), go(z) } |
3 | F | 11.4 " " reducing registers and instructions | Minsky, 1967, 11.4 (p.207) | |
{ inc(r), jdecnz(r, z), go(z) } |
3 | F | alt jump-version of above, equivalent. Mnemonic for Jump-and-decrement-if-not-zero | Minsky, 1967, 11.4 (p.207) | |
{ inc(r), jzdec(r, z), go(z) } |
2 | T | Minsky's 2 register program machine, mentioned on p.208, described in full in chapter 14 | Minsky, 1967, 14.1 (p.256) | |
{ inc(r), jzdec(r, z) } |
3 | T | Inferred machine based on replacing go(z) with w≡0 to simulate the 2 reg construction above | Minsky doesn't actually describe this, but it can be inferred from the various sections (14.1 + 11.1) | |
{ inc(r, z), jzdec(r, z) } |
2 | T | Minsky 1967 Theorem 141-1, "Generalised Minsky counter machine" (replaces go(z) with an extra arg. to inc(r, z)) | Minsky, 1967, 14.1 (p.257) | |
{ inc(r), jdecnz(r, z) } |
2 | T | Inferred machine based on Minsky 1967, ch.14 and 11.4 using the instruction ⊖ he calls "decrement and jump"; Expressed as "Jump-and-decrement-if-not-zero" above. This jdecnz() allows arbitrary jumps in a way jzdec() does not because the test result for a jump does not destroy all the information in a register, so *any* register can be used and have its data repaired at the jump target. |
Minsky, 1967, 14.1 (p.257) and 11.4 (p.207) | |
| ?? | 1 | T | Minsky one-register machine (M_*T) | Minsky, 1967, 14.2 (p.258) | |
| ?? | 2 | ??T | PROBLEM 14.2-2. -- M_T four -> three instructions | Minsky, 1967, 14.2 (p.258-9) | |
| ?? | 1 | ??T | PROBLEM 14.2-2. -- M_*T four -> three instructions | Minsky, 1967, 14.2 (p.258-9) | |
{ inc(r, z), dec(r, zTRUE, zFALSE) } |
2 | F | Best explicit generalisation (does not rely on any implicit 'next instruction' concept). Not minimal in sense defined here since zFALSE arg can be dropped (although removing zFALSE requires adding an implicit convention, so 'minimal' needs work). |
Used in Autopsy TC proof. Not in Minsky 1967 (AFAICT), but in Minsky 1961, Theorem Ia. (p.449). Using notation: Ij1 and Ij2.
| |
{ inc(z), jzdec(z), swap() } |
2 | T | Generalised Minsky Swap (TC, but not as currently specified on wiki) | Minsky Swap | |
{ inc(), jzdec(z), swap(), go(z) } |
2 | T | Minsky Swap with 'simple' inc and extra go(z) (required for TC) | ||
{ inc(), jzdec(z), swap(z) } |
2 | T | Minsky Swap with 'simple' inc and extended swap(z) to also branch | I just made it up... | |
{ inc(r), dec(r), while(dec(r)), if(dec(r)) } |
n | - | PMMN | Portable Minsky Machine Notation | |
{ inc(r), dec(r), while(dec(r)), if(dec(r)) } |
3 | F | Minimal register PMMN | ||
{ inc(r), dec(r), while(dec(r)) } |
3 | T | Minimal register and instruction PMMN (~ equiv 3 cell bf) | ||
{ inc(), dec(), next(), prev(), while() } |
3 | ? is bf minimal FWIW | 3 cell bf | 3 cell Brainfuck | |
{ inc(r), jzdec(r, z) } |
3 | T | Szewczyk notation for Minsky machine | Szewczyk notation for Minsky machine | |
{ inc(r), dec(r), while(r) } |
3 | T | ALWCIDFEC, basically 3 cell bf with "registers" | ALWCIDFEC | |
{ inc(), jzdecnext() } |
4 | T? | Autopsy -- TC proof uses 2 reg { inc(r, z), jzdec(r, zTRUE, zFALSE) } system which is definitely TC. |
Autopsy | |
{ incjnz(r, z), dec(r) } |
2 | T | Incdecisive Machine: incjnz(r, z) = "increase,-then-jump-if-not-zero". TC with two registers because it can relatively directly simulate the { inc(r), jdecnz(r, z) } 'not-zero-jump' set above. Test and jump is moved to the inc() command. |
Incdecisive Machine |
"Minimal" here means that no single element from { a register, an instruction, an argument to an instruction } can be removed and have the system remain Turing complete.
To remove one of these and have the system remain TC, another element MUST be added to compensate for some necessary functionality.
A non-minimal system can have at least one element from { a register, an instruction, an argument to an instruction } removed and remain TC.
Bibliography
- Minsky, Marvin L. (1961) "Recursive Unsolvability of Post’s Problem of 'Tag' and Other Topics in Theory of Turing Machines." Annals of Mathematics, vol. 74, no. 3, 1961, pp. 437–55. JSTOR, https://doi.org/10.2307/1970290.
- Minsky, Marvin L. (1967) Computation: Finite and Infinite Machines.
Notes
TODO: Adding implicit actions to instructions, and changing the range of allowed values to arguments (see Minsky's PROBLEM 14.2-2.) also has an effect on the power of a system. Try to incorporate these factors into the analysis. Thinking of (instruction, unique input) as individual instructions is perhaps the way to go. z should always be finite, and preventing c (arbitrary value) as an argument will avoid infinities.
2 reg PMMN Examining why 2 register PMMN appears non-TC I began to suspect it might be -- to simulate arbitrary jumps with while(), you should be able to store some extra state and direct execution to code located anywhere. This extra state could be Godel prime encoded into one or more extra virtual registers in one of the physical data registers and tested to take the correct path. However... 2 register PMMN is clearly a more limited version of Minsky's TC 2 register counter machine (can only jump with 'while', not arbitrary go(z)) and it seems likely that the restrictions on how data can be stored and accessed could prevent this. Simulating go(z) behaviour with while() and only two registers may require go(z). This feels like the same problem I encountered when trying to use 2 reg PMMN to copy / duplicate a value to another virtual register -- I couldn't get out of an inner loop to the next stage without losing all my data...
At any rate, learning how to code _anything_ for a 'normal' 2 register counter machine seems a pre-requisite for trying to simulate something in an even more restricted version. Once the basics are sorted out, it should be "relatievly easy" to demonstrate whether arbitrary branch simulation is possible or not, with the 2 register and while() restrictions. I'm suspecting it's not, since it would imply 2 cell bf is also TC, and the current wisdom seems to be that it's not.
while() prevents jumps from 'crossing' paths. Execution looks like it can always progress forwards 'inwards' to further nested loops. Perhaps a simple halt() command would help in some / all situations? Maybe a tight inner infinte loop to indicate "I'm done computing, and have nowhere else to go". Autopsy claims to be TC and does not halt, that seems a problem, but I'm not generally opposed to introducing conventions to indicate something meaningful, if the condition is unambiguous. (not claiming a 'tight infinite loop' is necessarily well defined, it might be, in some contexts.)