MiniMAX Turing-completeness proof
From Esolang
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, 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. 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, one word per line. ('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 @ < > [ ] & 1 0
Fixup number 40 4 4 20 16 16 8 8
MiniMAX code 1 1 1 1 1 1 1 1
-4 -7 1 -2 -2 -2 -5 -5
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 9 1
-2 -4 -4 -2 -1 -1
1 1 1 1 1 1
1 1 1 1 1 1
13 1 fix 1
-2 -4 -2 -2
1 1 1 1
1 1 1 1
1 fix 1 1
-4 -2 -4 -2
1 1 1 1
1 1 1 1
9 1
-1 -2
1 1
1 1
13
-2
1
1
1
-6
1
1
1
-1
1
1
1
-2
1
1
1
-4
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.
