4
$\begingroup$

How to construct my proof and generally what should I aim to get when showing a function is $\mu$-recursive? Should I transform it in some of the basic functions using the given operators?

For example, how should I proceed with the following one:

$\phantom{AAAA}pred(x) = undef$, if $x = 0$
$\phantom{AAAA}pred(x) = x - 1$, if $x > 0$

How should I handle the $undef$-part?

$\endgroup$
2
$\begingroup$

$\mu$-recursive functions are partial functions because of the minimization operator. Without minimization, you get primitive recursive functions, and they're total. So an undefined value can only arise because the minimization operator is involved somehow. For example, you can define $$\mathrm{undef} := \mu(1)$$ where $1$ is the constant function (with arity $2$) whose value is $1$.

In general, to prove that a function is µ-recursive, you proceed as you would to prove that an object is a member of a class. You demonstrate that the object can be built according to the rules of that class, possibly using objects that other people have already proven to be members.

$\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.