1
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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.

$\endgroup$

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.