3 ms·
The halting problem is that there is no algorithm possible that can answer, for all programs and all inputs, whether that program with that input will halt. He
by codebje 7y ago
The halting problem is that there is no algorithm possible that can answer, for all programs and all inputs, whether that program with that input will halt.
Here is my program:
def fool(input):
while input:
pass
The input given to the program is your answer as to whether it halts given that input.
That's the gist of the proof that the halting problem is unsolvable. Whatever the algorithm or method is used to answer the problem, you can take that method and "embed" it into the program to be verified, and invert the answer.
The halting program doesn't say you can't answer for many or even most programs and inputs, it just says there'll be at least one counter-example.
- thehappypm 7y agoThat's not really how it works, though. You could imagine writing an AI program that can read this program, figure out that it halts on the truthiness of the input, and handles this case flawlessly. The real proof is a bit of a head scratcher. Imagine we created such a function, doesHalt, that can read any program's source code and always figure out if the program will halt. This program can solve the halting problem -- it always produces a solution, either a True or a False. Feed it your fool program, it can always solve it, for any arbitrary input. So what happens if we run create this little head scratcher function, that takes no input: def headScratcher(): if doesHalt(headScratcher): while 1: pass This program halts if doesHalt() says it doesn't halt, and does not halt if doesHalt says it does halt. These are both contradictions -- proving that such a doesHalt function cannot actually exist.