Problem Solving in Automata, Languages, and Complexity

4.7 Pairing Functions and G6del Numberings 209

Then, it is clear that r(item(n, l), item(n, 2)... , item(n, k)) = n. Thus, 7
is onto. Note that we have shown in addition that we can decode 7 by a
primitive recursive function item. That is, item(n,i) is the unique ni such
thatforsomenr ,..., ?-&1,ni+l,..., nk,T(n1,..., nk)=n,ifl<i<Z(n)+l.
Finally, from the primitive recursiveness of X, we get that 71; is-primitive
recursive and, from the monotonicity property of z, we know that 7 also
satisfies the monotonicity property. q

We write (721,722,.. ., nk) to denote r(T(n~,n2,.. .,nk)) and [nl, n2,.. .,

nk] to denote +I, 722,... , nk). We also write size(n) to denote l(n) + 1; thus,

if 72 = [f-u,nal* l ‘7 nk], then size(n) = k.

The following are some more primitive recursive operations on sequences

of integers.

Example 4.35 Show that the following functions are primitive recursive:

(a) Eist(m, 0) = 0 and list(m, k) = [m, m,... , m], if k > 1.

• 
  
  
  
  • k
  
  
  
  

1

min{i 11 < - i 5 k, ni = m}

(b) find( [nl, l l l y nk], m) = if such an i exists,

0 otherwise.

1

[w, l l l 9 ni-l,m,ni+l,~nk]

(c) replace([nl,... , nk], m, i) = ifl<i<k, - -

[nl, l l l ,nk] otherwise.

(d) ConSeq([n1,...,nkl,[ml,.=.,mel) = [nl,...,nk,ml,...,me].

(e) subseq([m, l l l > nk], eq

- - [% , %+I^9 l l l 7 %+e-11 ifl<i<k, - - l<!<k-i+l - -

0 otherwise.

Solution. (a) We note that Zist(m, 0) = 0, list(m, 1) = (0, m) and, for k > - 1,

list(m, k + 1) = (k, (m, r(list(m, k)))).

(b) find(n, m) = (mini)l<il,i,,(,)[item(n, i) = m].

(c) Note that if 1 < - i < - s:ze(n), then

replace(n, m, i) = (mint)t<zist(n+m,size(n))[size(t) = si+--q

and (Vi)j<size(n)[j - = i or item(t,j) = item(n, j>]

and item(t, i) = m].

(Note: If n = [nl,... , nk] then n 2 ni for all 1 < i 5 k and so, by the

monotonicity property of Gijdel numberings, Zist(n + m, size(n)) is an upper

bound of the output of repZace(n, m, i).)

(d) We observe that conseq (n, m) can be expressed as follows:

(mint)tLzist(n+m,size(n)+size(m)) [si=(t) = six+) -I- si=(m)

and (Vi)l~~lsize(n)[item(t, i) = item(n, i)]

and (vj)l~jlsire(m)[item(t, n + j) =I item(m~.i)]*