MiniMAX Turing-completeness proof
The following is a proof that MiniMAX is Turing-complete, via analogy with extended Smallfuck.
Smallfuck becomes Turing-complete if the following command is added:
&(EXTEND)- Move one cell to the right and zero it. If at the rightmost cell of the tape, instead add a new cell to the right of the current cell and zero it.
(This command is required for Turing-completeness, because Smallfuck has a limited-length tape; note that MiniMAX also has a limited-length tape, so tape extension is something that needs to be compiled into a program explicitly. F2 cannot be used, because the boundedness of the tape.)
The proof is a construction. The MiniMAX program consists of a set of commands that mirror Smallfuck commands, followed by a data area, originally consisting of nothing but the word meaning 1, repeated four times for each data element of the original Smallfuck tape, plus four times extra. The program must start with (implementation-specific) commands to set up the current and previous commands so that the previous command was the first three words of the data area, and the current command is the first command in the code area. Then, Smallfuck commands can be translated mechanically as follows. The code is given in decimal.
('fix' and fixup numbers are explained below the table; 1 and 0 are optimizations that set or clear the current cell, respectively, but are not required for the proof).
| Command | Fixup number |
MiniMAX code |
|---|---|---|
* |
40 |
1 -4 1 1 1 -2 1 1 13 -2 1 1 1 -4 1 1 9 -1 1 1 13 -2 1 1 1 -6 1 1 1 -1 1 1 1 -2 1 1 1 -4 1 1 |
< |
4 |
1 -7 1 1 |
> |
4 |
1 1 1 1 |
[ |
20 |
1 -2 1 1 1 -4 1 1 1 -4 1 1 fix -2 1 1 1 -2 1 1 |
] |
16 |
1 -2 1 1 1 -4 1 1 fix -2 1 1 1 -4 1 1 |
& |
16 |
1 -2 1 1 1 -2 1 1 1 -2 1 1 1 -2 1 1 |
1 |
8 |
1 -5 1 1 9 -1 1 1 |
0 |
8 |
1 -5 1 1 1 -1 1 1 |
The resulting program needs fixup. The 'fix' in every [ command should be changed to 9 plus the total fixup value of all the commands between that [ and the corresponding ]. The 'fix' in every ] command should be changed to -27 minus the total fixup value of all the commands between that ] and the corresponding [.
If I/O is required, extensions to do this have to be added to both MiniMAX and Smallfuck. If the MiniMAX implementation allows the program to end, the code necessary to do this can be placed just after the code area.