That'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 in

That'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.