Problem Solving in Automata, Languages, and Complexity

4.7 Pairing Functions and G6del Numberings 213

3.

4.

Let 121, n2,... , nk are k nonnegative integers. Prove that if 1 5 ii <

i2<*** < it < _ k, then [nil, ni2,... , nit] < - [nl, n2,... , nk].

Assume that f(n, 0) = g(n) and f(n, m + 1) = h(n, f(n, k(m))) for

some primitive recursive g, h and k. Also assume that k(m) < ~72 for all

nz > 0. Prove that f is also primitive recursive. (Note that Solution 1

of Example 4.38 actually used this result.)

5. Show that the following functions are primitive recursive:

6.

(a) f (n, m) = the number of occurrences of integer m. in the sequence

= [nl,... , nk].

(b) i(n) = [dk,dk-1. , do], where &&-l l l l do is the decimal repre-

sentation of n (d.,:, g(2801) = [2,&O, 11).

We may extend the notion of primitive recursive functions to functions

from Z” to Z, where Z is the set of integers. All we need is to treat

a pair (nl, n2) as a represention of an integer in Z: If nl > 0, then

it represents n2, otherwise it represents -722. Show that the following

functions on integers are primitive recursive:

(a) inner(n, m) = the inner product of two k-dimensional vectors n

and m, if size(n) = size(m) = 2k (and it is 0, otherwise). (We

treat a list [q, f-32,... , r&] as a k-dimensional integer vector whose

ith element is the integer represented by (nzi-1, n& that is, it is

n2i if n2i,1 > 0, and is -n2i if n2i-1 = 0.)

(V det(n) = the determinant of the matrix n if size(n) = 2k2 for

some k > 1 (and it is 0 otherwise). (We treat [nl, n2,... , n+Jk2] as

a k x k integer matrix M with Mij equal to the integer represented

by the pair (n2(;-l)k+2j-1, n2(i-l)k+2j)a)

7.

8.

* 9.

We say a sequence n = [nl,... , r&k] is balanced if there exists a partition

of {1,2,.. ., k}intotwosubsetsBandC(i.e.,BUC={1,2,...,k}and

B n C = 0) such that CIcB ni = CjEc nj. Prove that the predicate [n

is balanced] is primitive recursive.

(a) Show that the function merge(n, m) that merges two sorted se-

quences into a single sorted sequence (and output 0 if any of the

two inputs is not sorted) is primitive recursive.

(b) Prove that sort is primitive recursive using the algorithm of merge

sort.

Assume that g : N -+ N and h : N2 -+ N are two primitive recursive

(b) Verify that if we use ~1 as a Godel numbering, then the functions

size, item and the functions of Example 4.35 all remain primitive

recursive. (Here, size(n) is the number of items in the sequence

n, excluding the trailing zeros.)