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.
Question Source : http://cs.stackexchange.com/questions/59693
0 comments:
Post a Comment
Let us know your responses and feedback