News for hackers. Stuff that matters.
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.
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.
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.