4 ms·
For any very simple arbitrary program, perhaps. But certainly not in general. That's sort of the point of the Halting Problem: you can't know because it is unde
by HCIdivision17 13y ago
For any very simple arbitrary program, perhaps. But certainly not in general. That's sort of the point of the Halting Problem: you can't know because it is undecidable.
Of course, there are simple and trivial programs that can be specifically analyzed, but we're definitely not to that level on any of the stuff under discussion here. The analogy really is pretty apt.
- dllthomas 13y agoThe halting problem is undecidable much like logic is incomplete. There will always be true statements we can't prove, and there will always be programs that might or might not halt. That doesn't mean that we can't prove lots of interesting things, it just means we can't promise to prove it when handed a program. We can try, and sometimes we'll succeed.
- XorNot 13y agoThe thing is a very simple program can be argued to be have been executed by the person's reading it. You know it halts because you look at the code, step through it mentally and - hey, it halts. But that's the nature of the problem: you know it halts because just executed it till it halts.
- dllthomas 13y agoYes, running them until they halt is one way of determining that a program halts on a given input. However, we can prove things do or don't halt without that. Consider running, on an idealized machine (so no overflows), while(i>0) { i * 2; } I think you would agree that this clearly never halts for any i > 0, and I think it also clear that we did not determine that by running it until it did not halt (because there is no such point). Turing proved that for some programs there is nothing we can do but run them and see. That doesn't mean that's all we can ever do.