Maybe the most prominent example of a $\mu$-recursive function that is not primitive recursive is the Ackermann function. But writing it out as a $\mu$-recursive function ("breaking it all the way down to the elementary operators") is rather complicated (see here).

I wonder what a most "simple" example of a $\mu$-recursive function that is not primitive recursive would be (without trying to define what exactly "simple" means). Or is the Ackermann function maybe maximally simple?


I know this is probably not what you wanted but the simplest function that comes to my mind is :

Let $f : x\mapsto 1$, the constant function equals to $1$.

Then let $g : y\mapsto \mu_xf(x)$.

$g$ is a function that never halts. $g$ is very simple and not primitive recursive.


The definition of the Ackermann function is simple, since it only takes a few lines. So, I presume you intend "simple" in a different sense, possibly in relation to the computational complexity of the function or the logical difficulty of proving its totality.

From the complexity point of view, there is an important result concerning many interesting complexity classes (belonging to the "folklore" of the subject), that is the following downward closure property: if a function f is computable in time O(g) and g is in a class C, than f is in C too (provided C is, say, closed w.r.t polynomials).

The result is a more or less trivial consequence of the complexity of Kleene's T-predicate (i.e. bound interpretation) for Turing machines, that is very low: not only it is primitive recursive: it is polynomial too.

So, if you know the upper bound g in time, you can run a bound interpreter for a suitable machine for the expected time g and hence simulate an arbitrary computation with a minimal overhead w.r.t. g.

This means that to look for a function that is not primitive recursive you need to look for a function whose computational complexity is not primitive recursive, and the simplest way to define such a function is to look for a function whose output grows sufficiently fast (since in order to produce an output n, you need at least time n).

From the logical point of view, the simplicity of the Ackermann function is manifested by the fact that it is easily definable in system T: by the well know characterization of Godel, this means that its totality can be already proved in Peano arithmetics, that is a relatively weak logical system.

Another way to understand how close is Ackermann function to the primitive recursive setting is the following. Suppose to relax a bit the condition of primitive recursion, allowing recursive calls where arguments are smaller in lexicographic order with respect to the arguments of the caller. Intuitively, this is already enough to ensure the well foundedness of the recursion, and hence the mathematical soundness of the definition.

With this slightly relaxed definition of "acceptable recursion", Ackermann function would become a perfectly legal definition.


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.