News for hackers. Stuff that matters.
Re:Russell's paradox and the Y combinator by tel on Wednesday June 03, 2015 @01:02AM (#9650675)
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!
Re:Russell's paradox and the Y combinator by CHY872 on Wednesday June 03, 2015 @04:49AM (#9651302)
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.
Re:Russell's paradox and the Y combinator by tel on Wednesday June 03, 2015 @10:45AM (#9652919)
Yes, of course. I'm not trying to prove anything, just to not that non-termination leads to suspicious looking logics.