Problem Solving in Automata, Languages, and Complexity

208 TURING MACHINES

0 0 1 3 6 10

I ).

0 1 2 3 4 5 I

Figure 4.18: The pairing function ~(i, j).

and, hence, G is primitive recursive. It follows that F(n) = Z(G(n)) is also
primitive recursive. Cl

We say a function f : Uk, i N” + N is a G6del numbering (of integer
sequences) if f satisfies the fonowing properties:

(i) (Bijectivity) f is one-to-one, onto.

(ii) (Primitive recursiveness) f 1 N”, the function f restricted to the domain

N”, is primitive recursive, for all k > - 1.

(iii) (Monotonicity) f (nl,... , n&l, ni, ni+l,... , nk) < f(nl,... , n&l, ni+l,

%+1, “‘7 nk) , for all 1 < - i < - k.

Example 4.34 Show that the function

is a G6deZ numbering.

Solution. We first verify that 7 is one-to-one. Suppose that T(n1, r-22,... , nkl)

• 
  
  
  
  • 7(77-w-732, l l ‘> mkz). By the one-to-oneness of 7r, we see that kl must be
    equal to k2. Next, we can prove that 7 is one-to-one on N” for each fixed
    k > - 1 by induction: If k = 1, then r(n) = (0, n ) is one-to-one. If k > 1, then
    r(nl,n2 ,..., nk) = (k4,(nl,r(r(n2 ,..., nk))). It follows from the one-to-
    oneness of 71 Nk-1 and r that TIN” is also one-to-one.
    Next, we check that for any integer n - > 0, there is a unique sequence
    (7-w-32, l l ‘9 r&k) such that T(n1, n2,... , nk) = n. First, we know that k =
    Z(n) + 1. Next, for each 1 < - i < - k, define
  
  
  
  

item(n, i) =

Z(#)(n)) if 1 < - i < - k - 1,

Ak)(n) ifi=k.