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

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

• In my answer at mathoverflow.net/a/53754/1946 I describe many natural hierarchies of sets of natural numbers (or equivalently, their characteristic functions) which transcend primitive recursion and even computability, and many or even most of those functions do not exhibit a fast-growing nature. – Joel David Hamkins May 7 '14 at 18:03
• Not directly related to your question, but maybe somewhat relevant: note that the inverse of a fast-growing function will usually be primitive recursive, so you won't find examples that way (see mathoverflow.net/questions/76037/…). – Noah Schweber May 7 '14 at 21:47
• Here's one idea: consider the function which takes two natural numbers $m$ and $n$ as input and returns $0$ if the Goodstein sequence on $m$ is longer than the Goodstein sequence on $n$ and $1$ otherwise. There's a naive algorithm to compute this, by evaluating both sequences and comparing lengths, but this is not primitive recursive, so one might conjecture there is no PR algorithm for this function. – aws May 8 '14 at 12:38
• I actually think now that the particular example in my previous comment doesn't work, but maybe something along similar lines will work, ie deciding if certain fast growing functions have a particular property. – aws May 8 '14 at 13:42

## 5 Answers

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Σ1 is obtained from Peano Arithmetic (PA) by restricting induction to Σ1 formulas; IΣ1 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Σ1 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Σ1. In other words, for every total computable function which isn't primitive recursive, there is a (nonstandard) model of IΣ1 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.

• +1. But François, are you saying in your last paragraph that, say, PA itself is an unnatural assumption? – Joel David Hamkins May 8 '14 at 0:39
• @Joel: Yes, I am, but I did use quotes for a purpose! In this context, "natural" is defined according to the (severely limiting) principle that a "natural" solution to a problem should not require more assumptions than the statement of the problem itself. – François G. Dorais May 8 '14 at 2:40

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.

• Just a few comments. The function of the "comes along... function" is (or can be) then the Turing machine execution time. For the function $f$ mentioned in the question (top), the "fast growing function" is the simulation time of $\phi_i(i)$ as a function of $i$. This is a way to show that no PR function can simulate all PR functions; a similar diagonal argument applies to every class of total recursive functions whose elements (descriptions of functions) can be effectively enumerated. This condition does not apply to the class of ALL total recursive functions. – Armando Matos May 8 '14 at 8:25

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. :) )

• I was thinking in the definition of the function, A(0,n)=n+1, etc. – Armando Matos May 7 '14 at 18:53
• The problems you mention are not recursive, the question was about total and not PR functions. Do you know any? – Armando Matos May 7 '14 at 18:56
• This is total. I think you are confusing the words "total" (every input has an output) and "recursive". If you mean "total recursive", you may want to edit your question to make that more clear. – Jason Rute May 7 '14 at 18:57
• Yes, I mean "total recursive", I'll edit the question, thanks! – Armando Matos May 7 '14 at 19:26

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.

• Very interesting. I couldn't yet look carefully at those papers, but correct me if I'm wrong: (1) the function which is total recursive and not PR is the complexity of a certain (verification) problem. (2) that function grows faster than any PR function - it is not "small". – Armando Matos May 9 '14 at 8:05
• I think this implies what you want, because every PR function can be simulated by a Turing machine bounded in time (and hence also in space) by the Ackermann function (modulo a constant). The functions themselves are all decision problems, so they are what you describe as small, and since they can't be simulated in Ackermann space, they are not PR. – aws May 9 '14 at 8:39

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.

• If this function is total then it's the constant $1$ function, which is primitive recursive. – Andreas Blass May 6 '17 at 13:50
• @AndreasBlass made some changes . How is it now? – ARi May 6 '17 at 14:04
• It's better in the weak sense that I don't know that this function, if total, is primitive recursive. But I also don't know that it won't be primitive recursive. Maybe some Collatz experts know, but my guess is that it's an open problem whether this function, if total, is PR. – Andreas Blass May 6 '17 at 14:12
• You don't need Line 5. Gerhard "Optimizing Compilers Don't Need It" Paseman, 2017.05.06. – Gerhard Paseman May 6 '17 at 15:08