Figure 12.5
Membership algorithm.
Theorem 12.4
Let M be any Turing machine. Then the question of whether or not L (M) is
finite is undecidable.
Proof: Consider the halting problem (M,w). From M we construct another
Turing machine that does the following. First, the halting states of M are
changed so that if any one is reached, all input is accepted by This can be
done by having any halting configuration go to a final state. Second, the original
machine is modified so that the new Machine first generates w on its tape,
then performs the same computations as M, using the newly created w and some
otherwise unused space. In other words, the moves made by after it has
written w on its tape are the same as would have been made by M had it started
in the original configuration q 0 w. If M halts in any configuration, then will
halt in a final state.
Therefore, if (M,w) halts, will reach a final state for all input. If (M,w)
does not halt, then will not halt either and so will accept nothing. In other
words, accepts either the infinite language Σ + or the finite language Ø.
If we now assume the existence of an algorithm A that tells us whether or not
L ( ) is finite, we can construct a solution to the halting problem as shown in