Norfuck
Norfuck is an extremely simple esoteric language created by Jack Eisenmann. His goal was to make a Turing-complete language with the fewest commands; however, the language falls short of being Turing-complete. The main principle of Norfuck is that it uses NOR logic to perform all calculations.
Machine memory
A Norfuck machine has 3 memory spaces:
- An infinitely long memory tape with a definite starting position. The tape contains a list of boolean values, true or false (1 or 0). A memory head points to a single value on the tape.
- A machine state, which is a single boolean value separate from the memory tape.
- An instruction tape which is shaped like a loop. Each command on this tape is executed in sequential order. The machine loops through the tape an infinite number of times; when the last command is executed, the next command to be executed is the first command.
Commands
There are 3 commands in Norfuck:
- >: Move the memory head 1 space to the right.
- <: If the data at the memory head is true, write true to the state. Move the memory head to the first cell.
- !: Write the inverse of the state to the value at the memory head. Set the state to false, and move the memory head to the first cell.
If I/O commands are included, there are 5 commands.
- ,: If there is input, write the next input character to the value at the memory head. Move the memory head to the first cell.
- .: Output the data at the memory head. Move the memory head to the first cell.
For each execution cycle of the machine, a different string of output values is given.
Example program
The program below counts up to 7 in binary. The first 3 cells on the memory tape store the digits of the binary number. To do so it inverts the first digit and generates a carry digit, then it performs XOR operations to find the next digit and AND operations to find their respective carry digits. Once the 3 new digits have been found, they are written back to the first 3 cells, and the cycle repeats.
>><>>>>>!>>>>><>>>>>>>>! ><>>>>>>!>>>>>>>><>>>>>>>! ><>>>>>>>><>>>>>>>>>! >>>>>><>>>>>>><>>>>>>>>! >>>>>>>><>>>>>>>>><>>>>! <>>>>>>!>>>>>>>><>>>>>>>! <>>>>>>>><>>>>>>>>>! >>>>>><>>>>>>><>>>>>>>>! >>>>>>>><>>>>>>>>><>>>! >>>>><>>!>><>>! >>>><>!><>! >>><!<!
This program compares two 3 digit numbers, and if they are equal, it will write true to the 32nd cell. If they are not, it will write false. The digits of the two numbers are stored in cells 1 through 3 and 4 through 6.
<>>><>>>>>>!<>>>>>><>>>>>>>!>>><>>>>>><>>>>>>>>! >>>>>>><>>>>>>>><>>>>>>>>>! ><>>>><>>>>>>!><>>>>>><>>>>>>>!>>>><>>>>>><>>>>>>>>! >>>>>>><>>>>>>>><>>>>>>>>>>! >><>>>>><>>>>>>!>><>>>>>><>>>>>>>!>>>>><>>>>>><>>>>>>>>! >>>>>>><>>>>>>>><>>>>>>>>>>>! >>>>>>>>><>>>>>>>>>! >>>>>>>>>><>>>>>>>>>>! >>>>>>>>>>><>>>>>>>>>>>! >>>>>>>>><>>>>>>>>>><>>>>>>>>>><>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>!
Computational class
Although Norfuck can simulate finite subsets of the 1D cellular automaton rule 110, this does not mean that it's Turing-complete, because it cannot simulate an infinite subset.
The main problem with programming in Norfuck is that each memory cell used must be programmed individually. For the rule 110 program, the behavior of each and every 1D automaton cell had to be programmed. It is possible to make a multiplexer or demultiplexer to read and write certain locations on the memory tape, but even in making the (de)multiplexer, each cell must be individually hooked up to the branching mechanism. This property makes Norfuck a very inefficient language. However, it is still many times more efficient than a lookup table, which stores the output values for all possible combinations of input values to the machine.