Problem Solving in Automata, Languages, and Complexity

4.7 Pairing Functions and G6del Numberings 211

by the following segment of a pseudo-Pascal program (where the inputs to f
are (nl,... , nk , m) and the output is f) :

f :=g(nl,-+k);

for i = 1 to m do

f :=h(nl,... >nk,i-- kf);

The general recursion operation considered in Theorem 4.37 above is equiv-

alent to the recursive calls that allow a procedure F(z) to call itself F(y) with

any y < 2. The above theorem shows that this type of recursive calls can also

be converted to a bounded-iteration loop structure. In practice, this type of

recursive calls can be implemented in a nonrecursive procedure with a stack

to store the values of F(O), F(l),... , F(z - 1). (The role of the stack is like

the function f” of Example 4.36.) The more general types of recursive calls

which allow F(z) to call F(y) f or any y may lead, in the worst case, to infinite

loops and hence do not preserve primitive recursiveness. Several other types

of recursions that preserve primitive recursiveness are studied in the exercises.

Example 4.38 The function sort : N + N maps a number [nl, n2,... , nk]

to the number [nPl, np2)... , nPk], where (~1 ,p2>... , pk) is a permutation of

(1 9 1 2 “‘1 k) such that nP1 < - nPz < + - l l < - nPk. Show that sort is primitive

recurszve.

Solution 1 (Selection sort). First, we define maxindex( [nl,... , nk]) to be the

least index 1 < - i < - k such that n; > - nj for all 1 < - j < - k. We note that

maxindex = (mini)l<i<,ize(n)(Vj)l<j<size(n)[item(n, -- - - j) < - item(n, i)].

Thus, maxindex is primitive recursive.

Next, we define g([nl,... , nk]) to be the list [nl,... , nk] with the maximum

item of [nl,... ,nk] removed. Let m* = maxindex( Then, g(n) can be

expressed as follows:

(i) If size(n) = 1, then g(n) = 0;

(ii) If size(n) > 1 and m* = 1 then g(n) = subseq(n, 2, size(n) 21);

(iii) If size(n) > 1 and m* = size(n) then g(n) = subseq(n, 1, size(n) 2 1);

(iv) If size(n) > 1 and 1 < m* < size(n), then

d n > = conseq(subseq(n, 1, m” - l), subseq(n, m + 1, size(n) - m)).

It follows that g is primitive recursive. In addition, it is easy to see that

g(n) < n for all n > 0 (see Exercise 3 of this section).

Now, we observe that sort(O) = 0, and sort(n + 1) can be expressed as

if size (n + 1) = 1 then n +^1

else conseq(sort(g(n + 1)) list(item(n + 1, maxindex(n + 1)) 1)).