Problem Solving in Automata, Languages, and Complexity

4.7 Pairing Functions and G&lel Numberings 207

To do this, we introduce coding functions that encode several integers into
one and use these functions to show that the seemingly more general recursion
operations actually preserve primitive recursiveness.
A function f : N2 + N is called a pairing function if it satisfies the
following properties:

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

(ii) (Primitive recursiveness) f is primitive recursive.

(iii) (MonotonicitY)2 f(i, j) < f(i + 1,j) and f(i,j) < f(i, j + 1), for all

i,jEN.

Suppose that f is a pairing function. Then, the functions Ef, rf : N + N,

defined bY f(lf (4, rf (4) = n, are well defined and are primitive recursive:

lf (n) = (mini)i<,(3j)j<,[f(i,j) = n],

rf (f-2) = (m&i)&[f(lf(n),j) = n]*

There are many pairing functions. We will use only one of them. (See

Exercise 1 of this section for others.)

Example 4.32 Show that the function T : N2 + N, defined by

n(i, j) = (i+j)(i+j+ 1) + j

2 7

is a pcairing function.

Solution. It is obvious that r is primitive recursive. Figure 4.18 shows that r is

indeed one-to-one and onto and satisfies the conditions that n(i, j) < n(i+l, j)

and n(i, j) < n(i, j + 1). cl

We write (i, j) to denote n(i, j), and l(n) and r(n) to denote E,(n) and

rn (n) , respectively.

Example 4.33 Show that the Fibonacci function is primitive recursive.

Solution. First, we transfer the double recursive definition of the Fibonacci

function into a single recursive definition of a more general function G. Define

G(n) = (F(n), F(n+ 1)). Then,

21n the lite rature, pairing functions are usually defined to be functions satisfying condi-

tions (i) and ( ii ) only, though most implementations also satisfy condition (iii).