Background: The following three functions (which map naturals to naturals) form a "complete basis" for universal computation, in the sense that any Turing machine can be simulated by iterating some finite composition of instances of these functions with some initial value of $n$: $$\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.

Question: Does the same result hold for the following three functions (which are approximations to $f_0,f_1,f_2$ respectively)? ... $$\begin{align} \hat{f}_0(n) & = n + [n \text{ is even}]\ n &= 2n \text{ IF }n \text{ is even ELSE }n\\ \hat{f}_1(n) & = n + [n \text{ is even}]\ 2n &= 3n\text{ IF }n \text{ is even ELSE }n\\ \hat{f}_2(n) & = \left\lfloor\frac{n}{2}\right\rfloor \end{align} $$

(Or perhaps the number of functions can be reduced without introducing undue complexity?)

NB: I don't know if this can be related, but it can be shown that the functions

$$\begin{align} f(n) &= 3 n\\ g(n) &= \left \lfloor \frac{n}{2} \right \rfloor \end{align}$$

are such that for all $x,y \in \mathbb{N_+}$, there exists a composition $F = g \circ g \circ \cdots \circ g \circ f \circ f \cdots \circ f $ with $\ y = F(x)$.

Motivation: The functions $f_0,f_1,f_2$ are designed to arithmetically mimic the exact behavior of three extremely simple operations on binary strings, which are nevertheless sufficient to simulate any Turing machine. It seems likely that simpler arithmetic operations can accomplish the same thing, although the proof may be elusive.

  • $\begingroup$ The fact that the 3 initial functions are considering integers as queues and the 3 other functions consider integers as stacks makes me feel that it will not work with them. Especially because with only one stack, you can't be Turing equivalent. But you can with one queue. $\endgroup$ – Xoff Aug 31 '15 at 5:59
  • $\begingroup$ @Xoff - I don't think that argument applies here. One starts with a single natural number $n$ and some composition $F$ of the basis functions, and the successive iterates $F^k(n)$ simulate the successive configurations of a Turing machine. (The situation is similar to Conway's FRACTRAN, in which a single function that maps naturals to naturals is iterated, with the iterates simulating successive states of a universal register machine.) $\endgroup$ – r.e.s. Aug 31 '15 at 13:20
  • 2
    $\begingroup$ Isn't any function formed by iterating some finite composition of instances of these functions total? Whereas some TMs' functions aren't total? $\endgroup$ – Quinn Culver Sep 1 '15 at 1:56
  • $\begingroup$ @QuinnCulver - Your wording is tricky. Any composition $F$ of the basis functions is total, but the iterates $F^k(n)$ may serve to define a partial function, by way of the fact that for some initial arguments the iterates may never reach a fixpoint (which would signify halting of the simulated TM). $\endgroup$ – r.e.s. Sep 1 '15 at 3:08
  • 2
    $\begingroup$ @user1667423 - I'm unaware of any new information relevant to this question. I've never created a bounty before, so allow me to make this my first. $\endgroup$ – r.e.s. Jan 29 '16 at 3:43

Apparently there is a universal program-machine (Minsky machine) with only one register that uses only the operations of multiplication and (conditional) division by integers 2 and 3. See section 14.2 in this paper by Minsky.

See also Minsky's model in here.


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.