How to handle an undefined case with µ-recursive functions?

Problem Detail: 

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?

Asked By : user8

Answered By : Gilles

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/59693

3200 people like this

 Download Related Notes/Documents