3 ms·
The easy way to think about the halting problem is imagine a program to do some sort of exponential time algorithm. At the end, it checks the result, and if it
by narrator 7y ago
The easy way to think about the halting problem is imagine a program to do some sort of exponential time algorithm. At the end, it checks the result, and if it meets some test, the program goes into an infinite loop. If you could determine that this program halts faster than it would take to run it, then you would know something about this difficult calculation without having to run it. This would be a way to speed up any algorithm!
- hairtuq 7y agoBut it's not only impossible to decide halting faster than the program would run, but impossible at all, a much stronger statement.
- pwdisswordfish2 7y agoIt's not really stronger, given that non-halting programs run forever.
- dtech 7y agoThat does not exclude possibility. Say determining the result takes 2^n and determining termination takes n!, you cannot speed up the algorithm using halting.
- tomstuart 7y ago“It seems be too good to be true” is a useful intuition, but it’s importantly different from “it is proven to be false”. (See also P ≠ NP.)