Integer is a Turing-complete integer-rewriting language. In this article the term number means non-negative integer.
Source code consists of a single number (non-negative integer). Input is also a single number. We create the main integer based on the source code and the input string, then we rewrite the main integer until the program halts, and finally we extract the output (which is also a single number).
First, we define the following helper functions to better explain how rewriting rules work.
Before the program starts, we need to initialize the main number. The main number is the number that we rewrite during the program execution. The main number is denoted by .
Let be the source code and let be the input. We define to be the smallest number such that
The main number is initialized to:
In each iteration, perform these steps until the program halts.
First, define the following numbers for this iteration:
If , then halt the program. Otherwise, define the following additional numbers for this iteration:
Finally, define for the next iteration:
When the program halts, the output is equal to:
Some examples have line breaks that are added for readability. Remove all whitespace characters before running on the interpreter.
Output constant 0
Decrement the input by 1
Zero stays zero.
Increment the input by 1
Divide the input by 2
Multiply the input by 2
Calculate the number of binary ones in the base-2 representation of the input
The shortest known program is approximately . It is too large to be pasted here.