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.
 A: 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$.
