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:

  1. 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.
  2. Define a new machine M2 corresponding to the pair M, w as follows.

    M2 = on input v:

    1. If v is not the same as w, halt. Otherwise continue.
    2. Feed v (meaning w in this case) to M and let M compute on w.
    3. 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.
  3. Feed the string <M2> into the decider D2.
  4. 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.