solve the halting problem. For example, given any M and w, we first modify M
to get in such a way that halts in state q if and only if M halts. We can do
this simply by looking at the transition function δ of M. If M halts, it does so
because some δ(q i ,a) is undefined. To get , we change every such undefined δ
to
δ(q i ,a) = (q,a,R),
where q is a final state. We apply the state-entry algorithm A to ( , q,w). If A
answers yes, that is, the state q is entered, then (M,w) halts. If A says no, then
(M,w) does not halt.
Thus, the assumption that the state-entry problem is decidable gives us an
algorithm for the halting problem. Because the halting problem is undecidable,
the state-entry problem must also be undecidable.
Example 12.2
The blank-tape halting problem is another problem to which the halting
problem can be reduced. Given a Turing machine M, determine whether or not
M halts if started with a blank tape. This is undecidable.
To show how this reduction is accomplished, assume that we are given some
M and some w. We first construct from M a new machine M w that starts with a
blank tape, writes w on it, then positions itself in a configuration q 0 w. After that,
M w acts like M . Clearly M w will halt on a blank tape if and only if M halts on w.
Suppose now that the blank-tape halting problem were decidable. Given any
(M,w), we first construct M w , then apply the blank-tape halting problem
algorithm to it. The conclusion tells us whether M applied to w will halt. Since
this can be done for any M and w, an algorithm for the blank-tape halting
problem can be converted into an algorithm for the halting problem. Since the
latter is known to be undecidable, the same must be true for the blank-tape
halting problem.
The construction in the arguments of these two examples illustrates an
to get in such a way that halts in state q if and only if M halts. We can do
this simply by looking at the transition function δ of M. If M halts, it does so
because some δ(q i ,a) is undefined. To get , we change every such undefined δ
to
δ(q i ,a) = (q,a,R),
where q is a final state. We apply the state-entry algorithm A to ( , q,w). If A
answers yes, that is, the state q is entered, then (M,w) halts. If A says no, then
(M,w) does not halt.
Thus, the assumption that the state-entry problem is decidable gives us an
algorithm for the halting problem. Because the halting problem is undecidable,
the state-entry problem must also be undecidable.
Example 12.2
The blank-tape halting problem is another problem to which the halting
problem can be reduced. Given a Turing machine M, determine whether or not
M halts if started with a blank tape. This is undecidable.
To show how this reduction is accomplished, assume that we are given some
M and some w. We first construct from M a new machine M w that starts with a
blank tape, writes w on it, then positions itself in a configuration q 0 w. After that,
M w acts like M . Clearly M w will halt on a blank tape if and only if M halts on w.
Suppose now that the blank-tape halting problem were decidable. Given any
(M,w), we first construct M w , then apply the blank-tape halting problem
algorithm to it. The conclusion tells us whether M applied to w will halt. Since
this can be done for any M and w, an algorithm for the blank-tape halting
problem can be converted into an algorithm for the halting problem. Since the
latter is known to be undecidable, the same must be true for the blank-tape
halting problem.
The construction in the arguments of these two examples illustrates an