3 ms·
Aye, I always think of the halting problem as "if the program is still running, you can't necessarily know if it will ever halt." If you see a program halt, aft
by baddox 15y ago
Aye, I always think of the halting problem as "if the program is still running, you can't necessarily know if it will ever halt." If you see a program halt, after a millisecond or after 10 years, then you've obviously proven whether or not it halts.
Also, while the halting problem doesn't necessarily say anything about bugs, there is a more general theorem that essentially says that you can't know in general if a program enjoys any non-trivial property (e.g. it prints a "1" at some point, it accesses the network, or it halts). I can't recall the name of the theorem, but the intuitive proof is similar to the halting problem's. This theorem does seem to hint that programs can't be proven to be bug-free in general.
- pmiller2 15y ago>...there is a more general theorem that essentially says that you can't know in general if a program enjoys any non-trivial property.... That would be Rice's theorem. http://en.wikipedia.org/wiki/Rice%27s_theorem http://en.wikipedia.org/wiki/Rice%27s_theorem