Re:What people get wrong about Bertrand Russell
by zajio1am on Tuesday January 07, 2020 @08:38PM
(#21987378)
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 .
[ Parent
| on HN ]
Re:What people get wrong about Bertrand Russell
by strbean on Wednesday January 08, 2020 @03:17PM
(#21995313)
Interesting, 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) ...