7
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.