0
$\begingroup$

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.

END

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?

Thanks

Improve this question
$\endgroup$
3
  • $\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, 2017 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, 2017 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, 2017 at 16:04

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.