- Turing kicked us out of Heaven (buttondown.com)
The halting problem is “undecidable”: there’s no algorithm which can tell you if an arbitrary program with an arbitrary input will halt or not. IE, if you give me a proposed “halt-detector”, I can inspect it and come up with a program and input for which it would give the wrong answer.
- Halting problem (Wikipedia)
In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. The halting problem is undecidable, meaning that no general algorithm exists that solves the halting problem for all possible program–input pairs. The problem comes up often in discussions of computability since it demonstrates that some functions are mathematically definable but not computable.