5 ms·
> I think the halting problem only tells you that you cannot, in general, opinionate on what the program does, without expending an amount of computational effo
by savingsPossible 5y ago
> I think the halting problem only tells you that you cannot, in general, opinionate on what the program does, without expending an amount of computational effort equivalent to running that program. A better counterpoint is that you can't know ahead of time what values will be returned by IO calls.
One corolary of the non-computability of the halting problem is that the problem "does this line ever run" is also non-computable
- PeterisP 5y agoThe halting problem only means that the problem "does this line ever run" is not computable for every case, since it's possible to construct undecidable cases. However, not all cases are undecidable and for most lines of most programs simple static analysis can indeed determine that certain lines will definitely run and certain lines won't. As long as you accept that the solution won't give a yes/no answer but yes/no/maybe, an automated system definitely can opiniate on what the program does; for example, by actually attempting to run the involved fragments for a limited time.