Most "simple" $\mu$-recursive function that is not primitive recursive

641 Views Asked by At

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?

1

There are 1 best solutions below

0
On

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.