MISC Turing-completeness proof

From Esolang
Jump to navigation Jump to search

The following program is a MISC interpreter for the esoteric programming language Brainfuck. It does not include the input/output instructions, but these are not needed to show that Brainfuck is Turing-complete, as Brainfuck without these instructions is isomorphic to the Turing-complete P'' (P prime prime) language.

The interpreter here runs on a MISC-16. The BF program should be appended (Unicode-encoded) to the end of the interpreter. The last word of the interpreter can be changed to alter where the BF program's memory cells are located (here it is set so as to give the program 30000 cells, as in many BF interpreters, but it can be moved to give more cells if the BF program isn't too long).

A commented version of the program is also available - see under External resources.

0000000000000101000000001001101000000000000000000100000000000001
0000000010010100000000000000000000000000010111010100000000001011
0000000000000101000000001001001100000000000000000100000000000001
0000000010001100000000000000000000000000000000010100000000100001
0000000010001001000000000000000000000000000000001100000000000001
0000000010000110000000001000011000000000000000010100000000000001
0000000000000101000000001000001000000000000110000100000000000001
0000000001111100000000000000000000000000010110110111111111111110
0000000001111000000000000111100000000000000000100100000000000010
0000000001110101000000000111010111111111111111100100000000000001
0000000001110001000000000111000100000000000000010100000000011010
0000000001101100000000000000000000000000000000011111111111111010
0000000001101000000000000110100011111111111111100100000000001011
0000000000000110000000000110011100000000001011000100000000000001
0000000001100000000000000000000000000000000000001000000000010110
0000000001011101000000000000000000000000000000001100000000000001
0000000001011010000000000101101011111111111111110100000000000001
0000000000000101000000000101011000000000010001000100000000000001
0000000001010000000000000000000000000000010110110111111111111110
0000000001001100000000000100110000000000000000100100000000000010
0000000001001001000000000100100100000000000000100100000000000001
0000000001000101000000000100010111111111111111110100000000001111
0000000001000000000000000000000000000000000000011111111111111010
0000000000111100000000000011110011111111111000110100000000000011
0000000000111011000000000011101111111111111111110100000000000001
0000000000110100000000000000000000000000000000011100000000001011
0000000000110000000000000011000011111111111111100100000000000011
0000000000101111000000000010111100000000000000010100000000000001
0000000000101000000000000000000000000000000000011100000000001000
0000000000100100000000000010010011111111111100010100000000000011
0000000000100001000000000000000100000000000000001100000000000001
0000000000011100000000000000000000000000000000011100000000000010
0000000000011001000000000000000000000000000000011100000000000001
0000000000001000000000000001011100000000011111000100000000000001
0000000000000101000000000001001100000000011111000100000000000001
0000000000000000000000000000000000000000000011010000000000000001
0000000000001010000000000000101000000000000000010100000000000001
0000000000000100000000000000000000000000000000011111111111011011
0000000000000000000000000000000000000000100110001000101011001101

External resources