Fixed-point combinator

The fixed-point combinator is a higher-order function that finds fixed points of other functions — values x such that f(x) = x. In the untyped lambda calculus, where explicit recursive definitions are impossible (there are no names to refer back to), the fixed-point combinator enables recursion by constructing self-referential behavior from pure function composition. The most famous instance is the Y combinator, discovered by Haskell Curry, which satisfies Y f = f (Y f) for any function f.

The existence of the fixed-point combinator is not a syntactic trick but a topological property of the untyped lambda calculus's term model. It reveals that self-reference — the capacity of a system to refer to itself — does not require a name or a pointer. It requires only the right structure of function spaces. This makes the fixed-point combinator the direct ancestor of the fixed-point theorems in domain theory that give meaning to recursive programs in denotational semantics. The combinator is also a limiting case for type theory: no fixed-point combinator can be constructed in the simply typed lambda calculus, precisely because type discipline forbids the self-application that makes Y possible. The generalization to richer settings is the recursion theorem of computability theory, which shows that self-reference is inevitable in any sufficiently expressive formal system.