Total Posts:12|Showing Posts:1-12

# Question about the Halting Problem

 Posts: 13,770 Add as FriendChallenge to a DebateSend a Message 4/18/2016 3:43:30 AMPosted: 2 years agoIn 1936 Alan Turing proved that it is impossible to create an algorithm for determining whether a given program would halt or continue to run forever on a given input. To do this, he employed the technique of reductio ad absurdum by showing that if such an algorithm were to exist, it could be altered in such a way that if one were to feed it into itself -- ask the algorithm whether it would halt on a given input -- any answer it gives would necessarily undermine its own validity. The altered program is to be exactly the same as the original in all but one respect: it has additional instructions on what to do once an answer has been reached. If it is thought that a given program would halt on some input, then the altered program (H+ for short) is to loop forever (not halt) while if it is thought that a given program would continue running forever on a given input, then H+ is to halt. When H+ attempts to calculate whether it would halt on a given input strange things start to happen. If it thinks it would halt, then it's supposed to loop forever in which case it doesn't halt. Conversely, if it thinks it would continue running forever then it's supposed to halt in which case it doesn't run forever. No matter what answer H+ comes up with it's always wrong, because the answer is no longer valid once H+ acts on its additional instructions.The part I don't get is why the failure of H+ to do its job has any relevance to the original algorithm. Can someone please explain Turing's reasoning?