Minus: Proof of Turing Completeness

To prove Minus is Turing complete I created a program to to convert any brainfuck program into Minus. Doing so shows that anything it can do, Minus can do too, which happens to be to be alot.

Each brainfuck instruction corresponds basically one to one in Minus except for [ and ].

] is pretty easy too, just subtract the number of statements from c to get to [

That leaves [. The basic idea is to backup the values of p and A. Then set p to -1, set A to -1 then subtract p by the old A. Now A is -1 only if the old value of A was 0. Now c can be subtracted by A to perform an if statement to decide to jump to ] or not. Finally backed up values of A and p must be restored.

Table summarizing conversion process. Replace %% by the number of Minus statements between the two %%'s. ** Shows where that jump lands. Note this code assumes b is set to -1.

Note that this process assumes that the brainfuck pointer never goes below 0 and that cell values are not negative. Brainfuck specification does not say that these things are allowed, but many brainfuck interpreters allow for such things. The conversion process could be tweaked to handle this correctly too.