News for hackers. Stuff that matters.
Re:The Y Combinator (no, not that one) – A Crash Course on L... by tel on Wednesday September 10, 2014 @09:37PM (#8300408)
Well, in 1936 Church invented the LC in order to serve as a foundational logic for mathematics. This was around the time that Hilbert's Program was attempting to totally mechanize reasoning through rich logical languages and Church wanted to use LC to define the notion of "efficiently computable" which was part of Hilbert's specification.

The Y-combinator was discovered originally as a flaw in the LC. It meant that you couldn't use LC as a logical language because you could form infinite loops which are not just not efficiently computable (in a sense, har har) but also correspond to vacuous logical statements like "If A proves A then A is true" which, in the context of rules like reflexivity "If A then A" (provable in LC as λ x . x) is logical nonsense.

To be more clear, here's the Y combinator

    λ f . (λ x . f (x x)) (λ x . f (x x))
and here's the Y-combinator applied to `id = λ x . x`

    (λ x . (x x)) (λ x . (x x))
which reduces into itself—a dead loop and a logical inconsistency (named "omega" as the end of LC!)

Anyway, Church worked for the next 4 years to invent the Simply Typed Lambda Calculus which imposes a Russell-like typing discipline on the LC in order to outlaw the Y-combinator. This made LC more useful for logic (and indeed STLC models Gentzen's Natural Deduction logical system) but it threw away its ability to compute any "recursively enumerable" function. That latter thing was what eventually came to be the definition of "efficiently computable" (after corroboration between Church's LC, Turing's Turing Machines invented the next year).

And now we happen to care about writing programs which, in general, may be r.e. and so we use either untyped LC or typed LC which has logically unsound recursion principles.

Re:The Y Combinator (no, not that one) – A Crash Course on L... by anatoly on Thursday September 11, 2014 @02:47AM (#8301198)
> (λ x . (x x)) (λ x . (x x))

This shows an infinite loop in lambda calculus evaluation. It can be arrived at independently (and I'd be surprised if it hadn't been) just by trying to build the simplest expression that doesn't reduce. Why do you need the Y combinator for this?

Re:The Y Combinator (no, not that one) – A Crash Course on L... by tel on Thursday September 11, 2014 @08:17AM (#8302112)
It had been. Everyone was just talking about the Y-combinator so I derived from there, but Omega was first.

Once you have any fixed-point, though, deriving the others is trivial. The explosive self-referential nature of your system has been uncovered.

Re:The Y Combinator (no, not that one) – A Crash Course on L... by eruditely on Thursday September 11, 2014 @12:00AM (#8300809)
Can you recommend me to any further reading regarding this or good literature? I've always meant to keep up with that, but aside from source papers is there a good overview of essentially what you're explaining? ie Further reading about Hilbert's Program.
Re:The Y Combinator (no, not that one) – A Crash Course on L... by tel on Thursday September 11, 2014 @09:39AM (#8302455)
The Stanford Emcyclopedia of Philsophy is usually a good source. If you're in Boston I'm going to be giving a Papers We Love talk on this stuff next week.