[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

• A language is recursively enumerable if there exists a Turing machine that accepts every string in the language and does not accept any string not in the language.
• A language is recursive if there exists a Turing machine that accepts every string in the language and rejects every string not in the language.

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);
else
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`.
Q.E.D.

Copyright © 1996 by David Matuszek
Last modified Apr 14, 1996