Re:Russell's paradox and the Y combinator
by skybrian on Tuesday June 02, 2015 @09:32PM
(#9650089)
I've read that languages for mathematical reasoning (such as Coq) are not Turing-complete to avoid issues like this. We can tolerate the possibility of infinite loops when we actually execute a program and see that it returns an answer, but apparently programs used as proofs aren't actually run, so type-checking needs to eliminate this sort of paradox.
[ Parent
| on HN ]
It's true! The reasoning is fairly simple, though.
In such a language, types classify terms and types correspond to theorems. The type/theorem for a fixed point is
fix : forall a . (a -> a) -> a
which as a theorem reads: "for any proposition A, if we can prove 'if A, then A' then we can prove A". Hopefully it's now clear why having 'fix' in your prover language won't work!Not quite. You're appleaing to the Curry-Howard correspondance, which is neat but is not used by many theorem provers. Furthermore,
> fun fix (f : 'a -> 'a) : 'a = fix f;
val fix = fn: ('a -> 'a) -> 'a
The trick is that all functions must be total, which is the crux of the matter (and why the Y-combinator exhibits the paradox, because it allows nontermination). This is why we have stuff like the polymorphic lambda calculus, in which termination is guaranteed and the Y-combinator is untypeable.Yes, of course. I'm not trying to prove anything, just to not that non-termination leads to suspicious looking logics.
Re:Russell's paradox and the Y combinator
by curryhoward on Tuesday June 02, 2015 @10:41PM
(#9650263)
Correct. One way to think of it is that running the program produces a proof of the theorem. But since the program is guaranteed to terminate with a proof (since all functions are total in Coq), why run it at all? Type checking is sufficient.