[Overview] [Previous] [Next]
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.
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
WillHalt then we could build
Accepts. If we could build
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
Copyright © 1996 by David Matuszek
Last modified Apr 14, 1996