CS385, Theory of Computation
Undecidability of the Halting Problem

This page is located at http://www.cs.bc.edu/~alvarez/Theory/halting.html

Halting problem, first version

The halting problem is to determine, given a program P and an input x to that program, whether P successfully completes its computation on x in a finite number of steps. The halting problem is a special case of the general problem of program verification, consisting of determining whether a given program behaves correctly according to its specification.

The language version of the halting problem described above is to establish a membership test for the following language:

Halt = { <M, w> | M is a Turing machine, w is a string, and M accepts w after a finite computation }

In class I showed that this language Halt 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 and inputs, just that no one program can solve the problem for all programs and inputs.

Summary of the argument that the halting problem is undecidable

We prove undecidability of the above language Halt by contradiction. We assume that Halt is decidable and show that this assumption leads to an unrealizable conclusion, thus showing that our initial assumption must be incorrect. The argument is based on constructing a supposed decider machine that "can't make its mind up" about itself.

So, assume that Halt is decidable. Then there is a decider Turing machine D that decides Halt. Define a new machine GMA in terms of D as follows.

GMA = on input s:

  1. Check that s is of the form <M>, where M is a Turing machine. If not, reject s. Otherwise continue.
  2. Feed the string z = <M, <M>> to the decider D. D will accept z if M accepts its own string encoding <M> and D will reject z otherwise.
  3. If D accepts z, reject s. If D rejects z, accept s.
Since D is a decider, the above machine GMA 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 for every machine M, GMA accepts M if and only if D rejects z, which happens if and only if M does not accept the string encoding <M> of itself.

But what decision does GMA reach on its own string encoding <GMA>? By the design of GMA, GMA accepts <GMA> if and only if GMA does not accept <GMA>. This means that no consistent decision is possible in this case. This contradiction shows that our original assumption that Halt is decidable must be wrong. We've therefore proved that Halt is undecidable.