Integer

Integer

Paradigm(s)	Integer-rewriting
Designed by	User:Hakerh400
Appeared in	2020
Computational class	Turing complete
Major implementations	Interpreter
File extension(s)	.txt

Integer is a Turing-complete integer-rewriting language. In this article the term number means non-negative integer.

Overview

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).

Rewriting rules

First, we define the following helper functions to better explain how rewriting rules work.

Helper functions

${\begin{aligned}f_{1}\left(x,y,z\right)&={\begin{cases}\left(y\mod x\right)+x\cdot \left(\left(z\mod x\right)+x\cdot f_{1}\left(x,\left\lfloor {\frac {y}{x}}\right\rfloor ,\left\lfloor {\frac {z}{x}}\right\rfloor \right)\right),&y+z\neq 0\\0,&y+z=0\end{cases}}\\f_{2}\left(x,y\right)&={\begin{cases}\left(y\mod x\right)+x\cdot f_{2}\left(x,\left\lfloor {\frac {y}{x^{2}}}\right\rfloor \right),&y\neq 0\\0,&y=0\end{cases}}\\f_{3}\left(x,y\right)&=f_{2}\left(x,\left\lfloor {\frac {y}{x}}\right\rfloor \right)\\f_{4}\left(x,y\right)&=x^{y}-1\\f_{5}\left(x,y\right)&={\begin{cases}1+f_{5}(x,\left\lfloor {\frac {y}{x}}\right\rfloor ),&y\not \equiv 0{\pmod {x}}\\0,&y\equiv 0{\pmod {x}}\end{cases}}\\f_{6}\left(x,y,z\right)&={\begin{cases}f_{6}\left(x,f_{3}\left(x,y\right),z-1\right),&z\neq 0\\f_{2}\left(x,y\right),&z=0\end{cases}}\\\end{aligned}}$

Initialization

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 $n$.

Let $R$ be the source code and let $I$ be the input. We define $e>1$ to be the smallest number such that

$R\equiv 0{\pmod {e}}$

The main number is initialized to:

$n=f_{1}\left(e,\left\lfloor {\frac {R}{e}}\right\rfloor ,f_{1}\left(e,0,f_{4}\left(e,I\right)\right)\right)$

Iteration

In each iteration, perform these steps until the program halts.

First, define the following numbers for this iteration:

${\begin{aligned}a&=f_{2}(e,n)\\b&=f_{2}(e,a)\end{aligned}}$

If $b=0$, then halt the program. Otherwise, define the following additional numbers for this iteration:

${\begin{aligned}c&=f_{3}(e,a)\\d&=f_{6}(e,c,b-1)\\g&=f_{2}(e,d)\\h&=f_{3}(e,d)\\i&=f_{3}(e,n)\\j&=f_{2}(e,i)\\k&=f_{3}(e,i)\end{aligned}}$

Finally, define $n$ for the next iteration:

$n_{\text{next}}={\begin{cases}f_{1}\left(e,f_{1}\left(e,h,c\right),f_{1}\left(e,\left\lfloor {\frac {j}{e}}\right\rfloor \cdot e+e-\left(j\mod e\right)-1,k\right)\right),&g\equiv 0{\pmod {4}}\\f_{1}\left(e,f_{1}\left(e,h,c\right),f_{1}\left(e,k,j\right)\right),&g\equiv 1{\pmod {4}}\\f_{1}\left(e,f_{1}\left(e,h,c\right),f_{1}\left(e,j\cdot e,k\right)\right),&g\equiv 2{\pmod {4}}\\f_{1}\left(e,f_{1}\left(e,f_{3}\left(e,h\right),c\right),f_{1}\left(e,\left\lfloor {\frac {j}{e}}\right\rfloor ,k\right)\right),&g\equiv 3{\pmod {4}}\land j\not \equiv 0{\pmod {e}}\\f_{1}\left(e,f_{1}\left(e,f_{2}\left(e,h\right),c\right),f_{1}\left(e,\left\lfloor {\frac {j}{e}}\right\rfloor ,k\right)\right),&g\equiv 3{\pmod {4}}\land j\equiv 0{\pmod {e}}\end{cases}}$

Extracting the output

When the program halts, the output is equal to:

$f_{5}(e,f_{3}(e,f_{3}(e,n)))$

Examples

Some examples have line breaks that are added for readability. Remove all whitespace characters before running on the interpreter.

Cat

0

Output constant 0

6

Infinite loop

70

Decrement the input by 1

Zero stays zero.

1152939097062396182

Increment the input by 1

309485009821345068994351110

Divide the input by 2

Rounds down.

9173994463960286046443283581208347763213219903346576852191495713375665208318111329792696452604547948
433686

Multiply the input by 2

9497114518078914140546986369588496999097156574631296911920877900450323135960192181045144766093709453
5660978509666584894170779877915934578796002563275301898134356610994269775078331695294614185134944592
1381741652194842497242855742293284839300722078236358064095580372493289042985035188303215631822733149
7180199102013493466141117373148941557708613501987350894765422523106464063285476558402824777007651467
1555285154428308898797515506032945032564446854433015556686006511836076831543072383949092673469495604
008688522888758168991401457612222023033157506841822272418164027655084280135958

Calculate the number of binary ones in the base-2 representation of the input

The shortest known program is approximately $1.6\cdot 10^{342102016}$. It is too large to be pasted here.

Interpreters

Interpreter