approach common in establishing undecidability results. A block diagram often
helps us visualize the process. The construction in Example 12.2 is summarized
in Figure 12.3. In that diagram, we first use an algorithm that transforms
(M,w)into M w ; such an algorithm clearly exists. Next, we use the algorithm for
solving the blank-tape halting problem, which we assume exists. Putting the two
together yields an algorithm for the halting problem. But this is impossible, and
we can conclude that A cannot exist.
Figure 12.3
Algorithm for the halting problem.
A decision problem is effectively a function with a range {0,1}, that is, a true
or false answer. We can look also at more general functions to see if they are
computable; to do so, we follow the established method and reduce the halting
problem (or any other problem known to be undecidable) to the problem of
computing the function in question. Because of Turing's thesis, we expect that
functions encountered in practical circumstances will be computable, so for
examples of uncomputable functions we must look a little further. Most
examples of uncomputable functions are associated with attempts to predict the
behavior of Turing machines.
Example 12.3
Let Γ = {0,1, }. Consider the function f (n) whose value is the maximum
number of moves that can be made by any n-state Turing machine that halts
when started with a blank tape. This function, as it turns out, is not computable.
Before we set out to demonstrate this, let us make sure that f (n)is defined for
all n. Notice first that there are only a finite number of Turing machines with n