The following program is an interpreter for the esoteric programming language BF. It does not include the input/output instructions, but these are not needed to show that BF is Turing-complete, as BF 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).
Comments and whitespace have been added to the listing below to make it slightly easier to understand.
// check if the current character is ]
0000000000000101 0000000010011010 0000000000000000 0100000000000001
0000000010010100 0000000000000000 0000000001011101 0100000000001011
// if the current character is ], check if the current memory cell is 0
0000000000000101 0000000010010011 0000000000000000 0100000000000001
0000000010001100 0000000000000000 0000000000000001 0100000000100001
// if the current character is ] and the current memory cell is not 0, find the matching [
0000000010001001 0000000000000000 0000000000000000 1100000000000001
0000000010000110 0000000010000110 0000000000000001 0100000000000001
0000000000000101 0000000010000010 0000000000011000 0100000000000001
0000000001111100 0000000000000000 0000000001011011 0111111111111110
0000000001111000 0000000001111000 0000000000000010 0100000000000010
0000000001110101 0000000001110101 1111111111111110 0100000000000001
0000000001110001 0000000001110001 0000000000000001 0100000000011010
0000000001101100 0000000000000000 0000000000000001 1111111111111010
// check if the current character is [
0000000001101000 0000000001101000 1111111111111110 0100000000001011
// if the current character is [, check if the current memory cell is 0
0000000000000110 0000000001100111 0000000000101100 0100000000000001
0000000001100000 0000000000000000 0000000000000000 1000000000010110
// if the current character is [ and the current memory cell is 0, find the matching ]
0000000001011101 0000000000000000 0000000000000000 1100000000000001
0000000001011010 0000000001011010 1111111111111111 0100000000000001
0000000000000101 0000000001010110 0000000001000100 0100000000000001
0000000001010000 0000000000000000 0000000001011011 0111111111111110
0000000001001100 0000000001001100 0000000000000010 0100000000000010
0000000001001001 0000000001001001 0000000000000010 0100000000000001
0000000001000101 0000000001000101 1111111111111111 0100000000001111
0000000001000000 0000000000000000 0000000000000001 1111111111111010
// check if the current character is >
0000000000111100 0000000000111100 1111111111100011 0100000000000011
// if the current character is >, move the memory pointer right
0000000000111011 0000000000111011 1111111111111111 0100000000000001
0000000000110100 0000000000000000 0000000000000001 1100000000001011
// check if the current character is <
0000000000110000 0000000000110000 1111111111111110 0100000000000011
// if the current character is <, move the memory pointer left
0000000000101111 0000000000101111 0000000000000001 0100000000000001
0000000000101000 0000000000000000 0000000000000001 1100000000001000
// check if the current character is -
0000000000100100 0000000000100100 1111111111110001 0100000000000011
// if the current character is -, set a temporary variable to 1
0000000000100001 0000000000000001 0000000000000000 1100000000000001
0000000000011100 0000000000000000 0000000000000001 1100000000000010
// if the current character is +, set a temporary variable to -1
0000000000011001 0000000000000000 0000000000000001 1100000000000001
// subtract the temporary variable from the current memory cell
0000000000001000 0000000000010111 0000000001111100 0100000000000001
0000000000000101 0000000000010011 0000000001111100 0100000000000001
0000000000000000 0000000000000000 0000000000001101 0000000000000001
// skip to the next character
0000000000001010 0000000000001010 0000000000000001 0100000000000001
0000000000000100 0000000000000000 0000000000000001 1111111111011011
// variables - temporary, temporary, program counter, memory pointer
0000000000000000 0000000000000000 0000000010011000 1000101011001101
For purists, here’s the code without the comments and whitespace:
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