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