4 ms·
I think that the difference is that Gödel's theorem related to the general case, and not the specific case. For example, the Halting Problem (which is, I admit
by SamBam 10y ago
I think that the difference is that Gödel's theorem related to the general case, and not the specific case.
For example, the Halting Problem (which is, I admit, what I first thought of when I read this) proves that there is no general algorithm that can state whether any program will halt for any input.
However, it says nothing about whether you can prove that a specific program will halt for any input. You can easily make programs that are guaranteed to halt, provably.
- peterbonney 10y agoI guess my thought was that if they are moving beyond very limited use cases and into broader ones (e.g. communication, which almost certainly involves very broad allowable inputs) then the existence of provably correct programs for small problems is less relevant. But as I'm starting to understand, it may be that this is still a very limited case compared to the theoretical general case, even if it is significantly more general than e.g. proving a given program will halt.