3 ms·
There is Rice's theorem (which is simple extension of Halting Problem and a basic theorem in computability theory), which states that all non-trivial, purely se
by zajio1am 7y ago
There is Rice's theorem (which is simple extension of Halting Problem and a basic theorem in computability theory), which states that all non-trivial, purely semantic properties of programs are undecidable. For more details, see https://en.wikipedia.org/wiki/Rice%27s_theorem https://en.wikipedia.org/wiki/Rice%27s_theorem .
- strbean 7y agoInteresting, but... The Wikipedia article gives 2 proofs for Rice's theorem. a) As a corollary of Kleene's recursion theorem. This proof seems to rely on quines, and therefore relies on the same principle of self-referential paradox? b) As a proof by reduction to the halting problem. I'm not very confident in my interpretation of (a) ...