204 TURING MACHINES
We now define three more operations on functions that preserve primitive
recursiveness. We call a total function R : ((0, l}*)” -+ (0, 1) a Boolean
function or a predicate. Recall that we identify the integer 1 with TRUE and
0 with FALSE. Therefore, if R(nl ,... , nk) is a predicate, then the expression
R(n1,.•. , nk) is equivalent to the expression [R(nl,... , nk) = l]. In addition,
if a formula defines a predicate, we often write the formula, instead of the
name of the predicate, to represent the predicate.
(3n)[n2 = m] to denote the value of the predicate
For instance, we write
s(m) = { :,
if (3n)[n2 = m],
otherwise.
Theorem 4.29 Suppose that f : N”+l -+ N is a primitive recursive predi-
cate. Then, the following functions are also primitive recursive.
(a) g(nl,... , nk, m) = (t%)i<mf(nl,... ,nk,i). (we say g is defined fromf by the operation of bounded iniversal quantifier.)
(b) h(nl,... , nk, m) = (ji)i<,f(nl,... , nk, i). (we say h is defined fromf by the operation of bounded existential quantifier.)
(mini)i<rnf (nl, l. l , nk, ;)
(c) t(nl, l s +k,m) =I
if (3i)i<mf(nl,-+k,i), -
0 otherwise,(We say t is defined from f by the operation of bounded minimization.)
Proof. All three functions can be defined by primitive recursion from f:
(a) g(nl,ynk,0) = f(nl,-+k,O), and
g(w***, nk,m+l)=[f(nl,...,nk,m+l) andg(nl,...,nk,m)].
(b) h(nl,-,nk,o) = f(nl,-+k,o), and
h(n1,*-, nk,m+l)=[f(nl,...,nk,m+l) o?++l,...,nk,m)].(c) t(nl,... , nk, 0) = 0, and
+-Jl,.**, nk,m+ 1) = [if (ji)i<,f(nl,. -. .,nk,i) then t(nl,.. .,n,m)
else if f (nl,... ,nk,m+l) then m+l ekeO]. 0The above three operations are very useful for proving functions being
primitive recursive.
Example 4.30 The following functions are primitive recursive.
1
1zj ifn>O,(a) cPo+--v-q = (^0) otherwise.
(b) mod(m) n) = { ;;” - ‘?Y ’ n e~we
.
(c) prime(n) =
1 if n is a prime,
0 otherwise.