5.5 Recursion Theorem 263
From the above analysis, we conclude that A cannot be recursive. 0
The following are some more examples of combining the diagonalization
technique with the recursion theorem to prove negative results.
Example 5.39 Let f : N + N be a recursive function. Show that there
exists an integer n such that W;, is a recursive set and the least integer m
such that W, = w, is greater than f(n).
Proof. First, we use diagonalization to construct a recursive set A (depending
on n) that is different from each W,, for all m < f(n). Next, we apply the
recursion theorem to find some n such that A = W,.
Formally, define&v-J) = 1
1 if m - < f(n) and q&(m) 4,
T otherwise.It is easy to see that g is partial recursive. By the
a constant n such that 4n(m) = s(m, n>* That is,recursion theorem, there is
Wn = {m 1 m 5 f(n),m E Wm}.
So, Wn is a finite set and, hence, a recursive set. For each m < f(n), m E W,
if and only if m E Wn, and so Wn # W,. It follows that if %m = W,, then
m must be greater than f(n). clExample 5.40 (Busy beaver) Let f(z) = min{n 1 4,&s) = x}. Show that f
is not a recursive function.For each string x E (0, l}“, f(z) is th e minimum Turing machine (in our
standard enumeration) that prints (I: from the empty input. Intuitively, we
may regard f( IX: ) as a string that encodes the minimum information of x
that is necessary in order to recover x by the universal DTM U. (Note: By
definition, U(f (x), E) = x .) The idea of the proof is that if f were recursive,
then we could use the DTM W that computes f to search for strings y
whose “minimum information codes” are much larger than the size of k!j,
and print such a string y. However, since we could get y by simulating Mf,
W would be essentially its minimum information code. Thus, this provides
us a contradiction. In the following, we present two proofs. The first one is an
informal construction and the second one is a formal proof by the recursion
theorem.Proof 1. Assume that f is a recursive function and is computed by a DTM
Mf For any fixed integer m, construct a DTM Tm, which, on the empty input
E, finds and prints the minimum 2 such that f(z) > 2”. More precisely, Tm
operates as follows: