242 COMPUTABILITY THEORY
f
f 4
f 3
f 2
fl
f 0
r -- r--T--~--i--
Lo:o’l’l’ -- -- .I. -- J--J-,
.
.
.
/^0
1 0 /
1 0 l/‘O I’0
/ /^0
0 0 0 /’ 0 /‘O
O/’ (^1) / /i 0
I
(^4) \ 0 1’1 1 1
\I
0 1 2 3 4
Figure 5.1: The diagonalization.
Since a function f is defined by an infinite number of parts f(O), f(l), f(2),...
and since these parts are independent of each other, we can satisfy the nth re-
quirement by making the nth part f(n) t o e 1 b d’ff erent from the corresponding
part of the nth function fn. This process can be seen more clearly in Figure
5.1. In this figure, the nth row contains the values of fn(0), fn(l),... , and
the function f is defined by taking the diagonal of the picture and changing
every element of it (hence the term &agoPlalization).
We remark that the term diagonalization is a little misleading, since we
do not have to define f to be the opposite of the diagonal. The construction
works as long as for every it > 0, there is a point x, such that f(xn) # fn (xn).
For instance, we may let x~-= n2 and let f(n2) = 12 fn(n2). Then, f still
satisfies all the requirements Ri, i > - 0. The values f(m) for those nz which
are not perfect squares can be used to satisfy other requirements.
The next example shows that the construction of object B could be made
by a machine as long as objects Ao, Al,... can be presented to the machine
in a uniform way.
We say a set A is co-r.e. if A is r.e.
Example 5.19 Show that there exists a co-r.e. set that is not r.e.
Proof. We are given a list VVO, M/1, W2,... , and need to find a set A that
is different from each of them. We may simply construct A one element at
a time: for each n, we let n E A if and only if n @ I/v,. That is, define
A = {n 1 n @ Wn}. Th en, A is not r.e., since it is different from every Wn,
n 2 0. In addition, A = {n 1 n E Wn} = {n 1 (3t)hult(n,n,t)}, and so A is
co-r.e. Cl
Corollary 5.20 (u) The set K = {n ( n E Wn} is r.e. but not recursive.
(b) The set I<0 = {(Y, 2> 1 a h a It s on input y} is r.e. but not recursive.