Are there natural, small, and total recursive functions that are not primitive recursive?

Question

In a sense the Ackermann function is not primitive recursive (PR) because it grows too fast.

Are there total recursive, not PR, small functions?

Using a diagonal argument, we may define a total recursive, not PR, and small (the codomain is {0,1}) function as: $f(n)=0$ if $\phi_n(n)\neq 0$, $f(n)=1$ if $\phi_n(n)=0$ where $\phi_i$ is the $i$th PR function. But, to me, this is not a "natural" function and furthermore it depends on the particular $\phi_i$ used.

And the question is: are there total recursive, not PR, natural, and small functions?

To be specific, let "small" mean "takes only the values 0 and 1", and let "natural" mean "recursively defined" (like the Ackermann function).

I apologize if this question is not appropriate to this forum.

Armando

Answer 1

There is a precise sense in which there aren't any "natural" examples of total recursive functions that aren't primitive recursive.

The system IΣ₁ is obtained from Peano Arithmetic (PA) by restricting induction to Σ₁ formulas; IΣ₁ is the weakest system that makes proper sense of basic computability theory. It is also the weakest subsystem of PA that proves that total computable functions are closed under primitive recursion and therefore IΣ₁ proves that every primitive recursive function is total.

Parson's Theorem says that the primitive recursive functions are precisely the computable functions that are provably total in IΣ₁. In other words, for every total computable function which isn't primitive recursive, there is a (nonstandard) model of IΣ₁ that thinks that this function isn't total.

The moral here is that in order to give a concrete example of a total computable function which isn't primitive recursive, you need to assume something somewhat "unnatural" in the sense that this assumption is not essential for reasoning about computable functions and primitive recursive functions.

Answer 2

If one does not require that the function is computable, then there is an abundance of natural answers, since there are of course many natural infinite binary sequences that are not primitive recursive or even computable.

So let us take it as part of the question that the function should be not only total, but also computable. So you want a total computable function that is not primitive recursive and does not exhibit the fast-growing behavior.

But in this case, let me argue that any total computable function $f:\mathbb{N}\to\mathbb{N}$ that is not primitive recursive is intimately connected with a fast-growing function. Namely, if $p$ is the Turing machine program computing $f$, then let $t(n)$ be the running time of $p$ on input $n$. It follows that $t$ is a computable function, but if $f$ is not primitive recursive, then $t$ is not bounded by any primitive recursive function. If $t(n)\leq g(n)$ and $g$ were primitive recursive, then $f$ would be primitive recursive, since

$\qquad\qquad n\mapsto $ the output of $p$ on $n$, if produced in fewer than $g(n)$ steps, otherwise $0$

is a primitive recursive function when $g$ is.

So every computable example function you seek comes along with a fast-growing computable non-primitive recursive function.

Answer 3

Many decision questions are natural, $0$-$1$ valued, and not primitive recursive (or even recursive). One of the most famous is Hilbert's 10th problem: determine if a polynomial $p$ in multiple variables with natural number coefficients has an integer root. (Update: What follows is my original encoding which I realize is for single variable polynomials --- for which Hilbert's 10th problem is decidable. One could easily adapt it to the multivariable case. However, since this doesn't answer the OP's implicit question, I will just leave it as it is.) For each $n \in \mathbb{N}$, let $n = 2^{a_0}\cdot 3^{a_1}\cdots p_{k_n}^{a_{k_n}}$ be is expansion into prime factors. Then define $$P_n(x) := a_{n_k} x^{n_k} + \ldots + a_1 x + a_0.$$ Now, let $\phi(n) = 1$ if $P_n(x)=0$ has an integer solution and $0$ otherwise. This is not computable.

Something similar can be done for the word problem for groups.

(Update: I just realized you defined "natural" as recursively defined. Do you mean $\phi$ is recursive? My example isn't recursive, but it is natural in a more natural sense of the word natural. :) )

Answer 4

Some searching turned up the paper Ph. Schnoebelen, Verifying Lossy Channel Systems has Nonprimitive Recursive Complexity. The author shows that various decision problems based on finite state machines with "lossy channels" are total recursive but not primitive recursive. I'm definitely not an expert in this area, but a quick read through the paper suggests that the basic idea of the proof seems to be that these finite state machines can simulate algorithms that are bounded in space by the Ackermann function. Hence a decision algorithm for their termination yields an algorithm computing the halting problem for Turing machines bounded in space by the Ackermann function.

Apparently, since that paper was published there have been a number papers describing decision problems that are recursive but not primitive recursive, of varying degrees of "naturalness," that work by showing the problem is equivalent to lossy channel systems. See this paper or this paper for example. (Again, I'm not an expert. This is just based on a quick search through the literature.)

By the way, the initial suggestion I made in the comments was completely wrong because length of Goodstein sequences is strictly increasing. However, I still think it's an interesting problem whether there's a proof along similar lines.

Answer 5

Line 1: Function Collatz(R1); out=0

Line 2: If Remainder(R1,2) = 0 Then Goto Line 6;

Line 3: If R1 = 1 Then Goto Line 8;

Line 4: R1 = Mult(R1,3) + 1;out=out+1

Line 5: Goto Line 2;

Line 6: R1 = Divide(R1,2); out=out+1

Line 7: Goto Line 2;

Line 8: Return(parity(out))

;

Lothar Collatz conjectured in 1937 that this "small" recursive (though non PR) function is total.