5 ms·
No, the parent is actually talking about the Halting Problem. It has been proven impossible to predict when a program will exit without actually executing the p
by BraveNewCurency 10y ago
No, the parent is actually talking about the Halting Problem. It has been proven impossible to predict when a program will exit without actually executing the program. (except in a few trivial edge cases)
https://en.wikipedia.org/wiki/Halting_problem https://en.wikipedia.org/wiki/Halting_problem
- beaconstudios 10y agoactually, the proof for the halting problem is rather esoteric in its demonstration. The claim isn't that you can't predict when most programs will end, but that it's possible to construct a scenario where the program goes out of its way to be unpredictable by running the prediction algorithm on itself and inverting the answer using an infinite loop.
- harveywi 10y agoMinor detail, but the undecidability Halting Problem strictly requires an infinite tape (infinite storage space). In "practice", if you could call it such, a computer with limited memory becomes a "linear bounded automaton" and the Halting Problem is decidable; cf. http://cs.stackexchange.com/q/22925 http://cs.stackexchange.com/q/22925 Of course, big enough memory can mean that it can be impossible to detect termination before the heat death of the universe - we are talking theory here.