Could you find an example of a complete $\mu$-recursive function that is not a primitive function?


1 Answer 1


There are two standard approaches: diagonalization and rate of growth.

The definition of primitive recursive functions (whichever one you use) allows enumerating them $f_1,f_2,\ldots$. Since each primitive recursive function is total, the function $f(n) = f_n(n)+1$ is recursive. It is clearly not primitive recursive.

The other approach is exemplified by the Ackermann function, which is clearly recursive but grows too fast to be primitive recursive.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.