Combinator

A combinator is a lambda term with no free variables.

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$.