= = = NORF**K TURING COMPLETENESS PROOF = = =
Language and Proof by Jack Eisenmann
Norf**k is not Turing complete. Although it is able to simulate the rule 110 1D automaton, it cannot simulate an infinite number of cells. The pseudo Norf**k program below simulates 16 cells in this rule set. Use the Norf**k translator and compiler to execute the code:
IN c0 c1 c2 c3 c4 c5 c6 c7 c8 c9 c10 c11 c12 c13 c14 c15;
c15 A; c0 B; c1 C;
A B C off0;
A c0 c1 off1;
c15 c0 c1 off2;
off0 off1 off2 i0;
c0 A; c1 B; c2 C;
A B C off0;
A c1 c2 off1;
c0 c1 c2 off2;
off0 off1 off2 i1;
c1 A; c2 B; c3 C;
A B C off0;
A c2 c3 off1;
c1 c2 c3 off2;
off0 off1 off2 i2;
c2 A; c3 B; c4 C;
A B C off0;
A c3 c4 off1;
c2 c3 c4 off2;
off0 off1 off2 i3;
c3 A; c4 B; c5 C;
A B C off0;
A c4 c5 off1;
c3 c4 c5 off2;
off0 off1 off2 i4;
c4 A; c5 B; c6 C;
A B C off0;
A c5 c6 off1;
c4 c5 c6 off2;
off0 off1 off2 i5;
c5 A; c6 B; c7 C;
A B C off0;
A c6 c7 off1;
c5 c6 c7 off2;
off0 off1 off2 i6;
c6 A; c7 B; c8 C;
A B C off0;
A c7 c8 off1;
c6 c7 c8 off2;
off0 off1 off2 i7;
c7 A; c8 B; c9 C;
A B C off0;
A c8 c9 off1;
c7 c8 c9 off2;
off0 off1 off2 i8;
c8 A; c9 B; c10 C;
A B C off0;
A c9 c10 off1;
c8 c9 c10 off2;
off0 off1 off2 i9;
c9 A; c10 B; c11 C;
A B C off0;
A c10 c11 off1;
c9 c10 c11 off2;
off0 off1 off2 i10;
c10 A; c11 B; c12 C;
A B C off0;
A c11 c12 off1;
c10 c11 c12 off2;
off0 off1 off2 i11;
c11 A; c12 B; c13 C;
A B C off0;
A c12 c13 off1;
c11 c12 c13 off2;
off0 off1 off2 i12;
c12 A; c13 B; c14 C;
A B C off0;
A c13 c14 off1;
c12 c13 c14 off2;
off0 off1 off2 i13;
c13 A; c14 B; c15 C;
A B C off0;
A c14 c15 off1;
c13 c14 c15 off2;
off0 off1 off2 i14;
c14 A; c15 B; c0 C;
A B C off0;
A c15 c0 off1;
c14 c15 c0 off2;
off0 off1 off2 i15;
i0 i0; i0 c0;
i1 i1; i1 c1;
i2 i2; i2 c2;
i3 i3; i3 c3;
i4 i4; i4 c4;
i5 i5; i5 c5;
i6 i6; i6 c6;
i7 i7; i7 c7;
i8 i8; i8 c8;
i9 i9; i9 c9;
i10 i10; i10 c10;
i11 i11; i11 c11;
i12 i12; i12 c12;
i13 i13; i13 c13;
i14 i14; i14 c14;
i15 i15; i15 c15;
OUT c0 c1 c2 c3 c4 c5 c6 c7 c8 c9 c10 c11 c12 c13 c14 c15;
When the pseudo code above is translated into raw Nof**k, the resulting code is given:
>>>>>>,>>>>>>>,>>>>>>>>,>>>>>>>>>,>>>>>>>>>>,>>>>>>>>>>>,>>>>>>>>>>>>,>>>>>>>>>>>>>,>>>>>>>>>>>>>>,>>>>>>>>>>>>>>>,>>>>>>>>>>>>>>>>,>>>>>>>>>>>>>>>>>,>>>>>>>>>>>>>>>>>>,>>>>>>>>>>>>>>>>>>>,>>>>>>>>>>>>>>>>>>>>,>>>>>>>>>>>>>>>>>>>>>,>>>>>>>>>>>>>>>>>>>>><!>>>>>><>!>>>>>>><>>!<><>><>>>!<>>>>>><>>>>>>><>>>>!>>>>>>>>>>>>>>>>>>>>><>>>>>><>>>>>>><>>>>>!>>><>>>><>>>>><>>>>>>>>>>>>>>>>>>>>>>!>>>>>><!>>>>>>><>!>>>>>>>><>>!<><>><>>>!<>>>>>>><>>>>>>>><>>>>!>>>>>><>>>>>>><>>>>>>>><>>>>>!>>><>>>><>>>>><>>>>>>>>>>>>>>>>>>>>>>>!>>>>>>><!>>>>>>>><>!>>>>>>>>><>>!<><>><>>>!<>>>>>>>><>>>>>>>>><>>>>!>>>>>>><>>>>>>>><>>>>>>>>><>>>>>!>>><>>>><>>>>><>>>>>>>>>>>>>>>>>>>>>>>>!>>>>>>>><!>>>>>>>>><>!>>>>>>>>>><>>!<><>><>>>!<>>>>>>>>><>>>>>>>>>><>>>>!>>>>>>>><>>>>>>>>><>>>>>>>>>><>>>>>!>>><>>>><>>>>><>>>>>>>>>>>>>>>>>>>>>>>>>!>>>>>>>>><!>>>>>>>>>><>!>>>>>>>>>>><>>!<><>><>>>!<>>>>>>>>>><>>>>>>>>>>><>>>>!>>>>>>>>><>>>>>>>>>><>>>>>>>>>>><>>>>>!>>><>>>><>>>>><>>>>>>>>>>>>>>>>>>>>>>>>>>!>>>>>>>>>><!>>>>>>>>>>><>!>>>>>>>>>>>><>>!<><>><>>>!<>>>>>>>>>>><>>>>>>>>>>>><>>>>!>>>>>>>>>><>>>>>>>>>>><>>>>>>>>>>>><>>>>>!>>><>>>><>>>>><>>>>>>>>>>>>>>>>>>>>>>>>>>>!>>>>>>>>>>><!>>>>>>>>>>>><>!>>>>>>>>>>>>><>>!<><>><>>>!<>>>>>>>>>>>><>>>>>>>>>>>>><>>>>!>>>>>>>>>>><>>>>>>>>>>>><>>>>>>>>>>>>><>>>>>!>>><>>>><>>>>><>>>>>>>>>>>>>>>>>>>>>>>>>>>>!>>>>>>>>>>>><!>>>>>>>>>>>>><>!>>>>>>>>>>>>>><>>!<><>><>>>!<>>>>>>>>>>>>><>>>>>>>>>>>>>><>>>>!>>>>>>>>>>>><>>>>>>>>>>>>><>>>>>>>>>>>>>><>>>>>!>>><>>>><>>>>><>>>>>>>>>>>>>>>>>>>>>>>>>>>>>!>>>>>>>>>>>>><!>>>>>>>>>>>>>><>!>>>>>>>>>>>>>>><>>!<><>><>>>!<>>>>>>>>>>>>>><>>>>>>>>>>>>>>><>>>>!>>>>>>>>>>>>><>>>>>>>>>>>>>><>>>>>>>>>>>>>>><>>>>>!>>><>>>><>>>>><>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>!>>>>>>>>>>>>>><!>>>>>>>>>>>>>>><>!>>>>>>>>>>>>>>>><>>!<><>><>>>!<>>>>>>>>>>>>>>><>>>>>>>>>>>>>>>><>>>>!>>>>>>>>>>>>>><>>>>>>>>>>>>>>><>>>>>>>>>>>>>>>><>>>>>!>>><>>>><>>>>><>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>!>>>>>>>>>>>>>>><!>>>>>>>>>>>>>>>><>!>>>>>>>>>>>>>>>>><>>!<><>><>>>!<>>>>>>>>>>>>>>>><>>>>>>>>>>>>>>>>><>>>>!>>>>>>>>>>>>>>><>>>>>>>>>>>>>>>><>>>>>>>>>>>>>>>>><>>>>>!>>><>>>><>>>>><>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>!>>>>>>>>>>>>>>>><!>>>>>>>>>>>>>>>>><>!>>>>>>>>>>>>>>>>>><>>!<><>><>>>!<>>>>>>>>>>>>>>>>><>>>>>>>>>>>>>>>>>><>>>>!>>>>>>>>>>>>>>>><>>>>>>>>>>>>>>>>><>>>>>>>>>>>>>>>>>><>>>>>!>>><>>>><>>>>><>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>!>>>>>>>>>>>>>>>>><!>>>>>>>>>>>>>>>>>><>!>>>>>>>>>>>>>>>>>>><>>!<><>><>>>!<>>>>>>>>>>>>>>>>>><>>>>>>>>>>>>>>>>>>><>>>>!>>>>>>>>>>>>>>>>><>>>>>>>>>>>>>>>>>><>>>>>>>>>>>>>>>>>>><>>>>>!>>><>>>><>>>>><>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>!>>>>>>>>>>>>>>>>>><!>>>>>>>>>>>>>>>>>>><>!>>>>>>>>>>>>>>>>>>>><>>!<><>><>>>!<>>>>>>>>>>>>>>>>>>><>>>>>>>>>>>>>>>>>>>><>>>>!>>>>>>>>>>>>>>>>>><>>>>>>>>>>>>>>>>>>><>>>>>>>>>>>>>>>>>>>><>>>>>!>>><>>>><>>>>><>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>!>>>>>>>>>>>>>>>>>>><!>>>>>>>>>>>>>>>>>>>><>!>>>>>>>>>>>>>>>>>>>>><>>!<><>><>>>!<>>>>>>>>>>>>>>>>>>>><>>>>>>>>>>>>>>>>>>>>><>>>>!>>>>>>>>>>>>>>>>>>><>>>>>>>>>>>>>>>>>>>><>>>>>>>>>>>>>>>>>>>>><>>>>>!>>><>>>><>>>>><>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>!>>>>>>>>>>>>>>>>>>>><!>>>>>>>>>>>>>>>>>>>>><>!>>>>>><>>!<><>><>>>!<>>>>>>>>>>>>>>>>>>>>><>>>>>><>>>>!>>>>>>>>>>>>>>>>>>>><>>>>>>>>>>>>>>>>>>>>><>>>>>><>>>>>!>>><>>>><>>>>><>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>!>>>>>>>>>>>>>>>>>>>>>><>>>>>>>>>>>>>>>>>>>>>>!>>>>>>>>>>>>>>>>>>>>>><>>>>>>!>>>>>>>>>>>>>>>>>>>>>>><>>>>>>>>>>>>>>>>>>>>>>>!>>>>>>>>>>>>>>>>>>>>>>><>>>>>>>!>>>>>>>>>>>>>>>>>>>>>>>><>>>>>>>>>>>>>>>>>>>>>>>>!>>>>>>>>>>>>>>>>>>>>>>>><>>>>>>>>!>>>>>>>>>>>>>>>>>>>>>>>>><>>>>>>>>>>>>>>>>>>>>>>>>>!>>>>>>>>>>>>>>>>>>>>>>>>><>>>>>>>>>!>>>>>>>>>>>>>>>>>>>>>>>>>><>>>>>>>>>>>>>>>>>>>>>>>>>>!>>>>>>>>>>>>>>>>>>>>>>>>>><>>>>>>>>>>!>>>>>>>>>>>>>>>>>>>>>>>>>>><>>>>>>>>>>>>>>>>>>>>>>>>>>>!>>>>>>>>>>>>>>>>>>>>>>>>>>><>>>>>>>>>>>!>>>>>>>>>>>>>>>>>>>>>>>>>>>><>>>>>>>>>>>>>>>>>>>>>>>>>>>>!>>>>>>>>>>>>>>>>>>>>>>>>>>>><>>>>>>>>>>>>!>>>>>>>>>>>>>>>>>>>>>>>>>>>>><>>>>>>>>>>>>>>>>>>>>>>>>>>>>>!>>>>>>>>>>>>>>>>>>>>>>>>>>>>><>>>>>>>>>>>>>!>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>!>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><>>>>>>>>>>>>>>!>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>!>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><>>>>>>>>>>>>>>>!>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>!>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><>>>>>>>>>>>>>>>>!>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>!>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><>>>>>>>>>>>>>>>>>!>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>!>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><>>>>>>>>>>>>>>>>>>!>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>!>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><>>>>>>>>>>>>>>>>>>>!>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>!>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><>>>>>>>>>>>>>>>>>>>>!>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>!>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><>>>>>>>>>>>>>>>>>>>>>!>>>>>>.>>>>>>>.>>>>>>>>.>>>>>>>>>.>>>>>>>>>>.>>>>>>>>>>>.>>>>>>>>>>>>.>>>>>>>>>>>>>.>>>>>>>>>>>>>>.>>>>>>>>>>>>>>>.>>>>>>>>>>>>>>>>.>>>>>>>>>>>>>>>>>.>>>>>>>>>>>>>>>>>>.>>>>>>>>>>>>>>>>>>>.>>>>>>>>>>>>>>>>>>>>.>>>>>>>>>>>>>>>>>>>>>.
When the user inputs 0000000000000001, the output of the program is as follows:
0000000000000001
0000000000000011
0000000000000111
0000000000001101
0000000000011111
0000000000110001
0000000001110011
0000000011010111
0000000111111101
0000001100000111
0000011100001101
0000110100011111
0001111100110001
0011000101110011
0111001111010111
1101011001111101
The pattern of 1's and 0's matches the expected result in rule 110. However, since only 16 cells are simulated here, the rule set will wrap around once it reaches the far left or right side.
Although the Norf**k programs is clearly quite inefficient, since the behavior of each individual cell must be programmed, the Norf**k program is considerably more efficient than creating a huge lookup table for the before and after states for all combinations of the 16 cells. If such a lookup table were created, each output case would require 2 bytes (2 * 8 bits = 16 bits, one for each cell). And since there are 2^16 possible input cases, there would need to be 2 * 2^16 bytes of output cases. That would be 131072 bytes. Excluding I/O commands, the Norf**k program which gives the same results is 4707 commands long. However, since there are only 3 kinds of commands (">", "<", and "!"), each command requires 2 bits, hence each byte of Norf**k stores 4 commands. 4707 / 4 = 1177 bytes of code for the Norf**k program. Clearly, when comparing the 131072 bytes of the lookup table and the 1177 bytes of the Norf**k program, one can see that the Norf**k program is many times more efficient than the lookup table.