5.3 Diagonalization 243
Proof. (a) K is the complement of set A of the above example. Since K = A
is not r.e;, I;;’ is not recursive (by Theorem 5.15).
(b) Suppose Ko were recursive, then K would also be recursive since
XK(x) = XKo((x,x))- Th us, by part (a), Ko is not recursive.^0
A decision problem is a problem whose answer is either yes or no. Every
decision problem corresponds to a language consisting of all inputs to which
the answer is yes. We say a decision problem is undecidcable (or, unsolvable)
if the corresponding language is not recursive. So, from part (b) of Corollary
5.20, we say that the problem of determining whether a given Turing machine
M halts on a given input string y (called the hcslting problem) is undecidable.
Example 5.21 We say Q partial recursive function f : (0, 1} + (0, l}
is extendable if there exists a recursive fianction g : (0, l} -+ (0, l} such
that g(x) = f(x) whenever f(x) 4. Sh ow that there exists a partial recursive
function that is not extendable.
Proof. If a partial recursive function f is extendable, then there exists an
integer n such that & is total and q& is the extension of f. So, we need
to construct a partial recursive function f that is different from every total
recursive function q&. To do this, define f(n) = 1+~5~(n).~
Then, f is partial recursive since f(n) = 11 a1 (n, n). (Recall that a1 is
the two-input function computed by the universal TM.)
Now, for every recursive function $n, f(n) J, because q& (x) 4 for every
x > 0. - It follows that f(n) = 12 & (n) and & is not the extension of f. •IWe have seen that {&} is an enumeration of all partial recursive func-
tions. Is there an enumeration of recursive functions? The answer is no. The
following example shows that we cannot enumerate all DTM’s that compute
recursive functions. Exercise 4 of this section gives an even stronger negative
result.
Example, 5.22 Show thut TOT = {n 1 W’ = (0, 1)‘) = {n 1 q& is recursive}
is not r.e.
Proof. The proof is a simple modification of the Example 5.21. Suppose, for
the sake of contradiction, that TOT is r.e. Then, by Theorem 5.13, there is a
recursive function g whose range is TOT. We need to find a recursive function
f such that f # &cn) for all n > 0. Define f(n) = 12 &c&n).
Since g(n) E TOT for all n 2 0, $+)( n ) is always defined and so f(n) is a
total function. In addition, f(n) = 1 L @(n,g(n)), and so f is recursive.
3Recall that when we write j(n) = 12 4n(n), it means that if & is defined on input n
with output y, then j(n) is equal to 12 y; otherwise, if & is not defined on input n, then
j(n) is undefined.