Problem Solving in Automata, Languages, and Complexity

212 TURING MACHINES

Thus, from Theorem 4.37, sort is primitive recursive. (See also Exercise 4 of

this section.) cl

Solution 2. We simply search for a new sequence which has the desired prop-
erties. First, we define the predicate perm(q) to mean that q = [ql, 42,... , qk]
is a permutation of [l, 2,... , ICI. That is,

Per??-+) = (Vi)l<i<size(s)(39)l<j<size(q)[item(Q,j) -- - - = ;I]*

Therefore, perm is primitive recursive.

Then, we observe that

sort(n) = (mint)t<,i,t(,,72)[size(t) = size(n) and sorted(t) and perm2(t, n)],

where sorted(t) is the predicate [t is sorted], and perm2(t, n) is the predicate

[t is a permutation of n]. We note that

sorted(t) = (Vi)l<i<site(t) -- A l[item(t, i) - < item(t, i + 1)],

T

Pe77-4, n> = (3) q<zist(si~e(n),size(n))[Perm(q) - and size(q) = size(n)

and (~i)l<i<size(7a)[item(t, -- i) = item(n, item(q, i))]].

herefore, both sorted

primitive recursive.

We remark that the

and perm2 are primitive recursive. It follows that sort

sim .pler expression

(~i)l<i<size(n) -- (3j)1<j<,i,,(t)[item(t, _ _ I-> = iten-+, ;)I

for perm,(t, n) does not work if the list n has duplicate elements ni = nj for

some i # j. cl

Exercises 4.7

1. Show that the following functions are pairing functions.
   (a) f$,m) = 2n(2m+ 1) - 1.
   Cb) f2 (% ml = max(n, m)2+m+g(m, n), where g(m, n) = n if m > - n,
   and s(m, n> =Oifn>m.


2. Let ~1 : Up1 - N’ -+ N be defined by f(nl,...,nk) = 2n13n2--pik,
   where pk is the &h prime.

(a) Show that the ~1 is onto, primitive recursive and monotone.

Also show that ~1 is almost one-to-one in the sense that if

Tr(nr,... , nk) = Tl(ml,... , me), and if k 5 e, then ni = rni for

all i, 1 < - i < - k, and mj = 0 for all j, k < j < - L