Y Combinator

lambda-calculus

Definition

Y Combinator

The $\mathbf{Y}$ combinator is a specific higher-order function (a combinator) and a fixed-point combinator in lambda calculus defined as:

$$\mathbf{Y}\equiv \lambda f.(\lambda x.f(xx))(\lambda x.f(xx))$$

The primary purpose of it is to implement recursion in lambda calculus, a formalism that lacks built-in recursive definition capabilities.

Step

A single step already shows the underlying recursive structure of the Y combinator:

$$\begin{array}{rl}\lambda f.(\lambda x.f(xx))(\lambda x.f(xx))& \stackrel{\beta }{\to }\lambda f.(f((\lambda x.f(xx))(\lambda x.f(xx))))\end{array}$$