Problem Solving in Automata, Languages, and Complexity

210 TURING MACHINES

(e) If 1 < - i < - size(n) and 1 < - l < - size(n) - i + 1, then we have

subseq(n, iJ) = ( mint)t<li,t(n,e)[sixe(t) = e

and (‘&&j<e[item(t, - - j) = item(n, i + j - l)]]. q

Note that all the proofs above, except for the function list, use only the
fact that sixe, item and list are primitive recursive and do not depend on the
particular Gijdel numbering used. In other words, they hold for all Gijdel
numberings.

Example 4.36 Show that the function f : N + N, defined by f(0) = 1,
f(n + 1) = f(O)“+’ + f (1)” +... + f (n)l, is primitive recursive.

Solution. Define f(n) = [f(n), f(n - l),... , f(O)]. We observe that

f(o) = [f @)I = list(f (o), I),

f”(n + 1) = conseq(Eist(f (n + l), l), j(n)).

Note that f(n + 1) can be written in terms of f(n) as follows:

f(n + 1) = k(item(f(n), i + l))i+l,

i=o

because item(?(n), i + 1) = f (n - i). Therefore, f(n + 1) can be expressed

in terms of f(n) (cf. E xercise 4(a) of Section 4.6). So, we conclude that f”

is primitive recursive. It follows that f(n) = item(f”(n), 1) is also primitive

recursive. q

The above example can be easily generalized to the general recursion op-

erations. We omit the proof.

Theorem 4.37 Assume that

f(n~,.+.,nk,O) =g(nl,-•,nk),

f(n1,-*, nk,m+ 1) = h(n1,...,nk,m,[fo,fi,...,f~l),

where fi is the abbreviation of f (nl ,... , nk, i), for 0 < i 5 m. If g and h are

primitive recursive, then f is primitive recursive. -

We remark that the primitive recursion operation is equivalent to the recur-

sive calls in a high-level programming language which limits a procedure F(z)

to recurisvely call itself F(y) only if y = x - 1. This type of recursive calls

can be easily converted to a bounded-iteration loop structure. For instance,

if f is defined from g and h by primitive recursion, then it can be computed