4.8 Partial Recursive Functions 215
Unbounded Minimization: Given a total predicate g : N”+l + (0, l}, define
function f : N” + N by
f (nl > ’ l l 7 nk) =
(minm)g(nl,*‘*~nk~m) if(3m)g(nl,**‘,nk,m),-r otherwise.
We say f is obtained by unbounded minimization operation from function g,
and simply write f(nl,-,nk) = (minm)g(nl,***,nk,m).
Partial Recursive Functions: A partial function f defined on Nk is called
partial recursive if it is an initial function or if it can be obtained from initial
functions by a finite number of applications of composition, primitive recur-
sion, and unbounded minimization. A partial recursive function f is also
called a recursive function if f is a total function.
Remarks. (1) Note that, in the above definition of unbounded minimization,
we required that this operation can only be applied to total functions. In-
deed, it is easy to obtain a nonrecursive function by applying the unbounded
minimization operation on a nontotal recursive function (see, e.g., Exercise 7
of Section 5.4).
(2) In the definition of partial recursive functions, we implicitly extended
the operation of composition to nontotal functions. For instance, if f is a
partial function on N and g(n) = 2n + 1, then the composition of g and f is
=zf (n) + 1h(n) = { T
if f(n) -1>
if f(n)? lFor convenience, we often simply write h(n)
partial functions f, g on N, we write f = g
either both f(n) and g(n) are undefined, or
and their values are equal.
There are two classes of computable sets
recursive functions.
Recursive Sets: A set A C - N” is recursive
= 2f(n) + 1. S imilarly, for two
to mean that, for each n E N,
both f(n) and g(n) are defined
related to the notion of partial
if its characteristic function
XA(nl I 732, l l l j nk) =
1, if(nl,n2,-.,nk) EA
0, if @I, 122,. l l ) nk)^4 A