Problem Solving in Automata, Languages, and Complexity

202 TURING MACHINES

Example 4.24 Show that the function minus : N2 -+ N, defined by

minus(m, n) = m 2 n =

1

0 ifm<n, -

m -n ifm>n,

is primitive recursive.

Solution. It suffices to show that pred(m) = m 2 1 is a primitive recursive

function, because minus can be defined by

minus(m, 0) = n:(m),

minus(m, n + 1) = pred(minus(m, n)).

To see that pred is primitive recursive, we note that pred(0) = 0 and

pred(m + 1) = m = nF(m,pred(m)).^0

Remark. Note that, in the above, a more formal proof for minus should be

minus(m, n + 1) = pred(ng(m, n, minus(m, n))).

For clarity, we omitted the function ~33 and used minus(m, n) directly. In

general, the projection functions 7ri k allow us to use any input anywhere in

the definition of a primitive recursive function, and the constant functions

Ii’;” allow us to use any constant anywhere we want. So, we can omit these

functions and simply write the inputs and constants wherever we need them.

Example 4.25 Assume that f : N + N is primitive recursive. Then, the

function g : N2 + N, defined by

sb-v-4 = f-(“,(m) def f(f(-*(f(m))*-)),

v ’

n

is also primitive recu rsive.

Solution. We note that

s(m, 0) = n:(m),

s(m, n + 1) = f (&-F 4).

So, g is defined from n: and f using primitive recursion, and hence is primitive

recursive. cl

Our goal of this and the next sections is to show that primitive recursive

functions are a very rich class of functions. To achieve this goal, we first

show that some control mechanisms of certain high-level programming lan-

guages are primitive recursive. We first consider some Boolean operations and

Boolean relations. We use 1 to represent TRUE and 0 to represent FALSE.