[Overview] [Previous] [Next]

The Halting Problem III

There is a simpler, though less satisfying, way to prove that the halting problem is insoluable. In fact, we have come very close to proving this already in our discussion of recursive and recursively enumerable functions.

Recall that

Proof. If a Turing machine WillHalt could be built, then we could readily build the machine

    function Accepts (M, w):
      if WillHalt (M, w) then
        return M (w);
        return False;

This Turing machine will always halt and always give the correct answer. If we could build WillHalt then we could build Accepts. If we could build Accepts, then we would have shown that every recursively enumerable language is recursive.

However, we showed earlier that there do exist recursively enumerable languages that are not recursive. (You might wish to review this argument.) Therefore, it must be impossible to build WillHalt.

Copyright 1996 by David Matuszek
Last modified Apr 14, 1996