Combinator

A combinator is a lambda term with no free variables.

The identity function represented as a closed lambda term. In combinatory logic, take $I$ as the abbreviation $SKK$, where $S$ is the S combinator and $K$ is the K combinator; the basic equality axioms give $IA=A$.

In lambda calculus, $S\equiv \lambda xyz.xz(yz)$ distributes its third argument to its first two arguments. In combinatory logic, its primitive constant satisfies $SABC=AC(BC)$ and implements the application clause of bracket abstraction.

In lambda calculus, the closed lambda term $K\equiv \lambda xy.x$ discards its second argument. In combinatory logic, its primitive constant satisfies $KAB=A$. The corresponding principal type in the simply typed lambda calculus is $\alpha \to (\beta \to \alpha )$.

The omega combinator is the divergent untyped lambda calculus termwhose only beta reduction reproduces $\Omega$.

An untyped lambda term $Y$ is a fixed-point combinator when $Yf{\equiv }_{\beta }f(Yf)$ for every term $f$.

Put $D=\lambda xf.f(xxf)$ and $\Theta =DD$. Then $\Theta f{\to }_{\beta }^{\ast }f(\Theta f)$. Unlike the Curry fixed-point combinator, every finite reduct retains a closed subterm $DD$. Contracting this subterm recreates one; every other generated redex substitutes a variable and preserves it. The Church-Rosser theorem therefore proves $Y/{\equiv }_{\beta }\Theta$.

With $A_f=\lambda x.f(xx)$, the combinator $Y=\lambda f.A_f{A}_f$ satisfies $Yf{\equiv }_{\beta }f(Yf)$. Every finite reduct of $Y$ is, up to alpha equivalence, $\lambda f.f^n(A_f{A}_f)$: the remaining copy of $A_f{A}_f$ is its only beta-redex.

Every lambda term $F$ has a fixed point: the termsatisfies $X{\equiv }_{\beta }F(X)$. Equivalently, a fixed-point combinator such assatisfies $YF{\equiv }_{\beta }F(YF)$ for every $F$.

The set of fixed-point combinators is recursively enumerable. Enumerate closed lambda terms and finite proofs of beta equivalence, and output $Y$ whenever a proof of $Yf{\equiv }_{\beta }f(Yf)$ appears for a fresh variable $f$.