Search code examples
lambda-calculusy-combinator

Y-Combinator definiton

I am trying to understand the fixed-point combinator. I think it is used by some languages to implement recursion. The main problem is that I couldn't get the next definition:

click here to see image

So please explain the image.

Solution

  • That is an implementation of the fixed-point combinator in lambda calculus (called a Y-combinator). It satisfies the equation

    enter image description here

    There isn't too much to "get" about the implementation other than it satisfies the above.

    The wikipedia entry here shows how the Y-combinator satisfies the above equation