# FRACTRAN for natural numbers

Is there a simple analogue of FRACTRAN that maps a natural number to a natural number, instead of mapping a list of fractions to a natural number?

One could use Gödel encoding to translate FRACTRAN directly to natural numbers only, but such a construction would probably be contrived. Is there a more elegant alternative?

I think a generalization of the Collatz function might be a candidate, but what is the simplest example of such a function that is Turing-complete?

For example, it is undecideable whether functions of the form

$$g(n)=a_in+b_i\qquad n\equiv i \pmod P$$

reach the number 1, for all $g$ and $n$, when iterated repeatedly.

Maybe this curiosity qualifies? ...

The following three functions (which map naturals to naturals) form a "complete basis" for universal computation: \begin{align} f_0(n) & = n + [n>0][n\ \text{even}]\ 2^{|n|_2} \\ f_1(n) & = n + [n>0][n\ \text{even}]\ 2^{|n|_2 + 1}\\ f_2(n) & = [n>0] \left\lfloor\frac{n-1}{2}\right\rfloor \end{align}

where $[...]$ are Iverson brackets and $|n|_2 = \lfloor\log_2(n+1)\rfloor$ is the number of digits in the bijective base-2 representation of $n$. (Note that $f_0, f_1$ are non-decreasing and $f_2$ is non-increasing, while $0$ is a fixpoint for all three functions.)

This is computationally universal because any Turing machine can be simulated by iterating some finite composition $F$ of instances of these three functions with some initial value of $n$. The iterates $F^k(n)$ simulate the evolution of the machine's configuration, eventually reaching $0$ iff the machine eventually halts.

It is undecidable whether the iterates $F^k(2)$ of an arbitrary composition eventually reach $0$.

NB: Any composition $F$ that simulates a universal Turing machine (and there will be infinitely many of these) serves as a single-function basis for universal computation (cf single-combinator bases for lambda terms).

Here is the original binary string version, in which all functions map $\tt\{0,1\}^* \to \{0,1\}^*$: \begin{align} g_0(s) & = \text{if }s \text{ begins with }\mathtt{1}\text{ then append } \mathtt{0}\text{ to }s\\ g_1(s) & = \text{if }s \text{ begins with }\mathtt{1}\text{ then append } \mathtt{1}\text{ to }s\\ g_2(s) & = \text{if }s \text{ is not empty then delete the beginning element of } s \end{align}

Now any Turing machine can be simulated by some finite composition $G$ of instances of these three functions, such that the iterates $G^k(n)$ simulate the evolution of the machine's configuration, eventually reaching $\epsilon$ (the empty string) iff the machine eventually halts.

It is undecidable whether the iterates $G^k(\mathtt{1})$ of an arbitrary composition eventually reach $\epsilon$.

• Very nice! Is there any way of reducing the number or complexity of the functions $f_i(n)$, while retaining universality? – user76284 Aug 30 '15 at 3:54
• @user1667423 - I strongly suspect that the arithmetic version can be simplified, but proving it is another matter. I've posted the question here. – r.e.s. Aug 30 '15 at 18:36