Problem Solving in Automata, Languages, and Complexity

4.6 Primitive Recursive Functions^201

We say f is the function obtained from g and h by the operation of primitive

recursion.

The class of primitive recursive functions over natural numbers can be

defined as follows:

(1) An initial function is a primitive recursive function.

(2) If g : N” -+ N and hl,...,hm : N” + N are primitive recursive

functions, then g o (hi,... , hm) is also a primitive recursive function.

(3) If g : N” + N and h : N”+2 -+ N are primitive recursive functions,

then the function f obtained from g and h by primitive recursion is also

a primitive recursive function.

(4) No other function is a primitive recursive function.

In other words, a primitive recursive function is a function that can be ob-
tained from the initial functions by a finite number of applications of compo-
sition and primitive recursion operations.

Example 4.21 Show that add(m, n) = m + n is primitive recursive.

SoZution. The function add can be defined by

add(m,O) = r:(m),

add(m, n + 1) = #(m, n, add(m, n))).

Thus, add can be obtained from ri and CT o ~33 by the operation of primitive

recursion, and so it is primitive recursive. Cl

Example 4.22 Show that mult(m, n) = mn is primitive recursive.

SoZution. The function mult can be defined by

mult(m,O) = c(m),

mult(m, n + 1) = add(nT(m, n, mult(m, n)), ‘lrg(m, n, mult(m, n))).

So, mult is primitive recursive, since it can be obtained from 5 and add o

( XT, ~33> by the operation of primitive recursion. Cl

Example 4.23 Show that constant functions I(j”(n~, l. l , nk) = j, k, j > - 1,

are primitive recursive.

Solution. Function 1j” can be defined by

(Note that the integer j is a fixed constant here.)