CS385, Theory of Computation
Second Version of the Halting Problem
This page is located at http://www.cs.bc.edu/~alvarez/Theory/halting2.html
Halting problem, first version
See my notes, which were posted previously.
Halting problem, second version
The second version of the halting problem is to determine, given a program P,
whether P completes its computation on every possible input in a finite
number of steps. We don't care whether the computations end in acceptance
or rejection.
The language version of the second version of the halting problem described
above is to establish a membership test for the following language:
Halt2 = { <M> | M is a Turing machine that halts
on all inputs after a finite computation }
In class I showed that this language Halt2 is undecidable.
In other words,
it is not possible to write a computer program that will solve the
halting problem. This is not to say that it is not possible to write
a program that will correctly determine halting for some reduced set
of programs, just that no one program can solve the problem
for all programs.
Summary of the argument that the halting problem is undecidable
We prove undecidability of the above language Halt2 by
showing that if it were decidable then so would the first version of
the halting problem, Halt, which we previously proved to be undecidable.
So, assume that Halt2 is decidable. Then there is a decider
Turing machine D2 that decides Halt2. Define a
decider machine D for the first version of the
halting problem in terms of D2 as follows.
D = on input s:
- Check that s is of the form <M, w>, where M is a Turing machine
and w is a string over the input alphabet of M.
If not, reject s. Otherwise continue.
- Define a new machine M2 corresponding to the pair M, w
as follows.
M2 = on input v:
- If v is not the same as w, halt. Otherwise continue.
- Feed v (meaning w in this case) to M and let M compute on w.
- If M's computation on input w halts and rejects w, loop indefinitely.
If M's computation on input w halts and accepts w, halt.
Otherwise continue looping like M is doing.
Notice that we've designed M2 in a clever way so that
the result of M's computation on input w is encoded in the halting
behavior of M2. Namely, M accepts w if and only if M2
halts on all inputs. In terms of language membership, this means that
<M, w> belongs to Halt if and only if <M2>
belongs to Halt2. In light of this fact, finish the
description of D's computation as follows.
- Feed the string <M2> into the decider D2.
- Return D2's decision.
Since D2 is assumed to be a decider, the above machine D is also
a decider: every step in its description may be completed in a finite number
of steps, and a definite decision is then reached for any input string s.
Notice that by construction D accepts <M, w> if and only if
M2 halts on all inputs, which happens if and only if M
accepts w. Therefore, D is a decider for the first version of the
halting problem, Halt. This is impossible, so our initial assumption
that the second version Halt2 of the halting problem
is decidable must be false.