Re:Why Philosophers Should Care About Computational Complexi...
by eru on Friday June 17, 2016 @06:33AM
(#11921791)
> We may not be able to prove mechanically whether any program halts, but if we can do it for any program appearing in practice, that may be good enough.
Alas, we can't even do that. Eg I have a simple program that systematically looks for a counterexample to Fermat's Last Theorem, and halts if it finds one.
We know now that this simple and comparatively natural program will never halt. But the proof is crazy.
Alas, we can't even do that. Eg I have a simple program that systematically looks for a counterexample to Fermat's Last Theorem, and halts if it finds one.
We know now that this simple and comparatively natural program will never halt. But the proof is crazy.