3 ms·
See also Rice’s theorem [0]: In computability theory, Rice's theorem states that all non-trivial, semantic properties of programs are undecidable. A semantic p
by gbacon 9y ago
See also Rice’s theorem [0]:
In computability theory, Rice's theorem states that all non-trivial, semantic properties of programs are undecidable. A semantic property is one about the program's behavior (for instance, does the program terminate for all inputs), unlike a syntactic property (for instance, does the program contain an if-then-else statement). A property is non-trivial if it is neither true for every computable function, nor for no computable function.
[0]: https://en.wikipedia.org/wiki/Rice's_theorem https://en.wikipedia.org/wiki/Rice's_theorem
- evincarofautumn 9y agoI think it’s worth noting that Rice’s theorem and the undecidability of the halting problem apply to arbitrary programs. In practice, the programs that humans write are very much non-arbitrary. Moreover, sometimes we’re happy to trade a bit of expressive power in exchange for stronger guarantees—like using a total/strongly-normalising language in which the answer to “Does this program terminate for all inputs?” is always “Yes”. In a similar vein, most real numbers are uncomputable, but we pretty much only care about the computable ones AFAIK.