4 ms·
> Even the halting problem is easily solved in practice. You don't grok what the halting problem is. What you're describing (I assume) is determining if a spec
by mcqueenjordan 7y ago
> Even the halting problem is easily solved in practice.
You don't grok what the halting problem is. What you're describing (I assume) is determining if a specific program is going to terminate. That's not the same problem.
From Wikipedia:
Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist.
- ahelwer 7y agoI "grok" very well what the halting problem is, thank you. It's colloquially used in the sense of being unable to tell whether a program terminates. For reference I direct you to early static analysis tool promo materials (ex. Coverity) which usually explicitly address the "doesn't this run into the halting problem?" question given its common occurrence.
- UncleMeat 7y agoThe entire field of static analysis is "solving" undecidable problems effectively and productively all the time. Just accept a few false positives or false negatives and suddenly the field opens up to be amazingly useful. Yes it isn't literally solving the halting problem. But I've had a weird number of people tell me that the stuff I work on doesn't work because of things they learned in undergrad.