Problem Solving in Automata, Languages, and Complexity

4.6 Primitive Recursive Functions^203

Example 4.26 Show that the following functions are primitive recursive:

ifx > - 1,

if x = 0.

(b) and(x, y) = { i $~e2s~nd ” ”

.

(c) Of(X, Y> = {

1 ifx>l ory>l,

0 otherwise. -

(d) if- then-eEse(x, y, x) = { i ZoftteFwise.

Solution. (a) neg(x) = minus(l,x).

(b) and@, Y) = neg(neg(mult(x, Y)>>*

(c> of-(x, Y) = neg(anq-%l(x), neg(Y)))*

(d) if-then-else(x, y, x) = add(mult(neg(neg(x)), y), mult(neg(x), x)). q

We often write “x and y” for and(x, y), “x or y” for or(x, y), and “if x

then y else 2’ for if- then-eZse(x, y, x>.

Example 4.27 Show that the following functions are primitive recursive:

Cb) gr(xy y> = { i

ifx > Y,

if x < ye

((9 w(x, Y) = { :,

.

g : ;?.

(4 qx, Y) = { :,

.

g ; ;I

(e) h(x, Y) = { ;

.

$; t ;I

Solution. (a) eq(x, y) = neg(add(minus(x, y), minus(y, x))).

(b) gr(x, Y) = neg(neg(min+-b Y>>>*

(c) geq(x, Y) = P-(x, Y) Or 4x7 Y>*

(d) qx, Y) = w(!Fq(x, Y>>*

(e) h(x, Y> = neg(gr(x7 Y>>* Cl

Example 4.28 For every k > - 1, the function maxk (nl, n2,... , nk) =

max{nl, n2,... , nk} is primitive recursive.

Solution. We can prove this by induction. When k = 1, maxl(nl) = n:(nl).

For k > 1,

mUXk(nl,...,nk) = if nk > maxk-l(nl,...Ynk--I)

then nk else maxk-‘(nl,.. .,nk-1). 0