states. This is because Q and Γ are finite, so δ has a finite domain and range.
This in turn implies that there are only a finite number of different δ’s and
therefore a finite number of different n-state Turing machines.
Of all of the n-state machines, there are some that always halt, for example
machines that have only final states and therefore make no moves. Some of the
n-state machines will not halt when started with a blank tape, but they do not
enter the definition of f . Every machine that does halt will execute a certain
number of moves; of these, we take the largest to give f (n).
Take any Turing machine M and positive number m. It is easy to modify M to
produce in such a way that the latter will always halt with one of two
answers: M applied to a blank tape halts in no more than m moves, or M applied
to a blank tape makes more than m moves. All we have to do for this is to have
M count its moves and terminate when this count exceeds m. Assume now that f
(n) is computable by some Turing machine F . We can then put and F
together as shown in Figure 12.4. First we compute f (|Q|), where Q is the state
set of M . This tells us the maximum number of moves that M can make if it is to
halt. The value we get is then used as m to construct as outlined, and a
description of is given to a universal Turing machine for execution. This tells
us whether M applied to a blank tape halts or does not halt in less than f (|Q|)
steps. If we find that M applied to a blank tape makes more than f (|Q|) moves,
then because of the definition of f, the implication is that M never halts. Thus we
have a solution to the blank-tape halting problem. The impossibility of the
conclusion forces us to accept that f is not computable.
Figure 12.4
Algorithm for the blank-tape halting problem.
This in turn implies that there are only a finite number of different δ’s and
therefore a finite number of different n-state Turing machines.
Of all of the n-state machines, there are some that always halt, for example
machines that have only final states and therefore make no moves. Some of the
n-state machines will not halt when started with a blank tape, but they do not
enter the definition of f . Every machine that does halt will execute a certain
number of moves; of these, we take the largest to give f (n).
Take any Turing machine M and positive number m. It is easy to modify M to
produce in such a way that the latter will always halt with one of two
answers: M applied to a blank tape halts in no more than m moves, or M applied
to a blank tape makes more than m moves. All we have to do for this is to have
M count its moves and terminate when this count exceeds m. Assume now that f
(n) is computable by some Turing machine F . We can then put and F
together as shown in Figure 12.4. First we compute f (|Q|), where Q is the state
set of M . This tells us the maximum number of moves that M can make if it is to
halt. The value we get is then used as m to construct as outlined, and a
description of is given to a universal Turing machine for execution. This tells
us whether M applied to a blank tape halts or does not halt in less than f (|Q|)
steps. If we find that M applied to a blank tape makes more than f (|Q|) moves,
then because of the definition of f, the implication is that M never halts. Thus we
have a solution to the blank-tape halting problem. The impossibility of the
conclusion forces us to accept that f is not computable.
Figure 12.4
Algorithm for the blank-tape halting problem.