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
Best Answer
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.