I understand what the halting problem describes, but I do not understand how the proof by contradiction associated with it proves that it is impossible to solve.

The proof by contradiction can be defined as having a function Halt() which could determine whether a program will halt. One could then call this function in a program called Program and halt if the program halts or otherwise loop forever.

Program (String x)

If Halt(x, x) then
 Loop Forever
Else Halt.


What I don't understand is why if Halt() returns true that it has to Loop forever. Why can't the Program return 0 or 1?


  • $\begingroup$ It loops forever, by construction, so that there is a contradiction. If it returned 0, then it is possible that the Halt() call will simply return True (for all we know) so that no contradiction happens. In other words, it is constructed to cover both cases (of Halt() returning True or False). $\endgroup$ – Omar Dec 9 '17 at 13:50
  • $\begingroup$ Thanks for the response. If I instead did if Halt(x,x) then return 0, why would this not be valid? $\endgroup$ – user81528 Dec 9 '17 at 15:34
  • $\begingroup$ The program would be okay, but the proof wouldn't work (if Halt returns True, no contradiction arises since the program will indeed terminate). See cs.stackexchange.com/a/38477/73821 for a proof sketch. $\endgroup$ – Omar Dec 9 '17 at 16:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy