Let
g (x,y) = x + y 3,
which is a total function. If x ≤ 3, then
y = 3 – x
is the result of the minimalization, but if x > 3, then there is no y ∈ I such that x
+ y – 3 = 0. Therefore,
µy(g (x, y)) = 3 – x, for x ≤ 3,
= undefined, for x > 3.
We see from this that even though g (x,y) is a total function, µy(g (x,y)) may only
be partial.
As the previous example shows, the minimalization operation opens the
possibility of defining partial functions recursively. But it turns out that it also
extends the power to define total functions so as to include all computable
functions. Again, we merely quote the major result with references to the
literature where the details may be found.
Definition 13.2
A function is said to be µ-recursive if it can be constructed from the basis
functions by a sequence of applications of the µ-operator and the operations of
composition and primitive recursion.
Theorem 13.5
A function is µ-recursive if and only if it is computable.
Proof: For a proof, see Denning, Dennis, and Qualitz (1978, Chapter 13).
The µ-recursive functions therefore give us another model for algorithmic