# Fixed-point combinator

A fixed-point combinator is a higher-order function \( Y \) that, applied to any function \( f \), returns a fixed point of \( f \), that is, a value \( x \) satisfying \( f(x) = x \). In symbols, \( Y f = f(Y f) \). Fixed-point combinators are central terms of the untyped lambda calculus and combinatory logic, where they supply recursion to a language that has no named definitions, and they are the reason every recursive equation in those systems can be solved.<sup>[1](https://plato.stanford.edu/entries/logic-combinatory/)</sup><sup> • </sup><sup>[2](https://www.funcp.org/wiki/y-combinator)</sup>

| Key fact | Detail |
|---|---|
| Defining property | \( Y f = f(Y f) \) for every \( f \); the equation holds up to β-equality, so both sides reduce to the same term<sup>[2](https://www.funcp.org/wiki/y-combinator)</sup> |
| Curry's Y | \( Y = \lambda f.(\lambda x.f(x\,x))(\lambda x.f(x\,x)) \); \( YF \) and \( F(YF) \) are β-equivalent, but neither reduces to the other<sup>[3](https://arxiv.org/abs/2504.19379)</sup> |
| Turing's Θ | \( \Theta = (\lambda xy.\,y(x\,x\,y))(\lambda xy.\,y(x\,x\,y)) \), with the stronger property \( \Theta F \rightarrow_{\beta}^{+} F(\Theta F) \)<sup>[4](https://www.cis.upenn.edu/~cis5110/notes/tcbook-comp.pdf)</sup> |
| Publication history | Turing's Θ was the first fixed-point combinator published (1937, *The p-function in λ-K-conversion*, Journal of Symbolic Logic 2); the Y combinator was first published by Rosenbloom in 1950<sup>[5](https://theory.stanford.edu/~blynn/lambda/quine.html)</sup> |
| Typed setting | No fixed-point combinator can be defined in the simply-typed lambda calculus, since it would permit a non-halting term and contradict normalization<sup>[6](https://academicweb.nd.edu/~dchiang/teaching/pl/2025/stlc.html)</sup> |
| Haskell's fix | `fix f` is the least fixed point of `f`, the least defined `x` such that `f x = x`, defined as `fix f = let x = f x in x`<sup>[7](https://hackage-content.haskell.org/package/base-4.11.1.0/docs/Control-Monad-Fix.html)</sup> |
| Enumeration | The set of fixed-point combinators is recursively enumerable, as a subset of non-standard fixed-point combinators, which is not<sup>[8](https://tidsskrift.dk/brics/article/view/21867)</sup> |

## Definition and the fixed-point theorem

In combinatory logic, \( \textsf{Y} \) appears among the standard combinators with the one-step reduction axiom \( \textsf{Y}x \triangleright_1 x(\textsf{Y}x) \), which states directly that \( \textsf{Y}x \) is a fixed point of \( x \).<sup>[1](https://plato.stanford.edu/entries/logic-combinatory/)</sup> The fixed-point theorem of the untyped lambda calculus and combinatory logic says that for any function \( M \) there is a term \( N \) such that \( MN = N \); the proof is immediate, because \( \textsf{Y}M \) can play the role of \( N \).<sup>[1](https://plato.stanford.edu/entries/logic-combinatory/)</sup> The importance of the combinator is that it ensures all functions have a fixed point and all recursive equations can be solved.<sup>[1](https://plato.stanford.edu/entries/logic-combinatory/)</sup>

The self-application \( x\,x \) inside the standard definitions is what makes them work, since it lets a function receive itself as an argument.<sup>[2](https://www.funcp.org/wiki/y-combinator)</sup> Many varieties of typed lambda calculus, along with type theory more broadly, make it impossible to build a fixed-point combinator, since no type exists whose terms are self-applicable.<sup>[9](https://ncatlab.org/nlab/show/fixed-point%2Bcombinator)</sup>

## The Y combinator

The most famous fixed-point combinator is the Y combinator, commonly attributed to [Haskell Curry](https://www.edgepedia.org/haskell-curry):<sup>[5](https://theory.stanford.edu/~blynn/lambda/quine.html)</sup>

\[ Y = \lambda f.(\lambda x.f(x\,x))(\lambda x.f(x\,x)) \]

Two β-steps show that \( Y g \) is a fixed point of \( g \): \( Y g \rightarrow_{\beta} (\lambda x.g(x\,x))(\lambda x.g(x\,x)) \rightarrow_{\beta} g((\lambda x.g(x\,x))(\lambda x.g(x\,x))) =_{\beta} g(Y g) \).<sup>[2](https://www.funcp.org/wiki/y-combinator)</sup> The equation holds up to β-equality, not by an actual reduction of \( Y g \) to \( g(Y g) \); both reduce to the same term, and neither \( F(YF) \rightarrow_{\beta}^{+} YF \) nor \( YF \rightarrow_{\beta}^{+} F(YF) \) holds.<sup>[2](https://www.funcp.org/wiki/y-combinator)</sup><sup> • </sup><sup>[4](https://www.cis.upenn.edu/~cis5110/notes/tcbook-comp.pdf)</sup>

**Attribution.** The credit is more tangled than the usual attribution suggests. Cardone and Hindley's history of the lambda calculus records that Turing's Θ was the first fixed-point combinator to be published, in 1937, and that the Y combinator was first published by Rosenbloom in 1950, in the form \( Y = \lambda x.W(Bx)(W(Bx)) \) where \( Wxy = xyy \).<sup>[5](https://theory.stanford.edu/~blynn/lambda/quine.html)</sup> However, in a 1929 letter to Hilbert, Curry wrote the term \( (\lambda y.N(yy))(\lambda y.N(yy)) \), with \( N \) representing negation, and Curry's use of that term dates back to that letter; he gave no explicit fixed-point combinator in print before Curry and Feys (1958).<sup>[5](https://theory.stanford.edu/~blynn/lambda/quine.html)</sup><sup> • </sup><sup>[10](https://www.sciencedirect.com/topics/computer-science/lambda-calculus)</sup> Curry's 1942 paper *The Inconsistency of Certain Formal Logics* introduced what is now known as [Curry's paradox](https://www.edgepedia.org/currys-paradox), built on the same self-application mechanism.<sup>[5](https://theory.stanford.edu/~blynn/lambda/quine.html)</sup>

## Turing's Θ and evaluation order

Turing came up with another fixed-point combinator that does not have the Y combinator's reduction disadvantage.<sup>[4](https://www.cis.upenn.edu/~cis5110/notes/tcbook-comp.pdf)</sup> Writing \( A = \lambda xy.\,y(x\,x\,y) \) and \( \Theta = AA \), one obtains \( \Theta F \rightarrow_{\beta}^{+} F(\Theta F) \) for any term \( F \), so Θ actually reduces to the fixed point rather than merely being equivalent to it.<sup>[4](https://www.cis.upenn.edu/~cis5110/notes/tcbook-comp.pdf)</sup> Turing published it in a one-page article, *The p-function in λ-K-conversion*, in the [Journal of Symbolic Logic](https://www.edgepedia.org/journal-of-symbolic-logic) in 1937, where he gave the formula \( \Theta \rightarrow \{\lambda vu.\,u(v(v\,u))\}\{\lambda vu.\,u(v(v\,u))\} \) with the property that if \( M \rightarrow \Theta(V) \) then \( M \) conv \( V(M) \).<sup>[11](https://www.pls-lab.org/Theta_combinator)</sup><sup> • </sup><sup>[12](https://ndl.ethernet.edu.et/bitstream/123456789/33594/1/80.pdf.pdf)</sup>

The distinction matters for evaluation strategy. The Y combinator works under normal order reduction, but under applicative order evaluation the self-application \( (\lambda x.F(xx))(\lambda x.F(xx)) \) reduces forever before \( F \) is ever called.<sup>[13](https://student.cs.uwaterloo.ca/~cs442/W25/notes/webnotes/Module-2/)</sup><sup> • </sup><sup>[2](https://www.funcp.org/wiki/y-combinator)</sup> The remedy is to wrap the repeated part in an abstraction so the evaluator cannot select it as the next redex; the resulting strict-language variant is known as the Z combinator, which delays the self-application behind a λ and works in call-by-value languages.<sup>[13](https://student.cs.uwaterloo.ca/~cs442/W25/notes/webnotes/Module-2/)</sup><sup> • </sup><sup>[2](https://www.funcp.org/wiki/y-combinator)</sup>

## Recursion without named definitions

The pure lambda calculus has no names for definitions, only [anonymous functions](https://www.edgepedia.org/anonymous-function), so a recursive definition such as factorial must be expressed differently: the recursive call is abstracted into a parameter, giving \( F = \lambda s.\lambda n.\,\text{if}\ n = 0\ \text{then}\ 1\ \text{else}\ n \times s(n-1) \), and factorial is then a function \( fact \) with \( fact = F\,fact \), a fixed point of \( F \). A fixed-point combinator produces one for any \( F \), so \( fact = YF \).<sup>[2](https://www.funcp.org/wiki/y-combinator)</sup>

Fixed-point combinators are not strictly required for recursion on the natural numbers: none was used in Kleene's 1936 λ-representation of the recursive functions.<sup>[10](https://www.sciencedirect.com/topics/computer-science/lambda-calculus)</sup> In combinatory logic, fixed-point combinators can also be defined from bases without a cancellator, as the definitions \( \textsf{Y}_1 = \textsf{BM}(\textsf{BWB}) \) and \( \textsf{Y}_2 = \textsf{W}(\textsf{B}(\textsf{BW}(\textsf{BT})))(\textsf{W}(\textsf{B}(\textsf{BW}(\textsf{BT})))) \) show; \( \textsf{Y}_1 M = M(\textsf{Y}_1 M) \) holds, while for \( \textsf{Y}_2 \) the stronger reduction \( \textsf{Y}_2 M \triangleright M(\textsf{Y}_2 M) \) holds, mirroring Curry's and Turing's combinators respectively.<sup>[1](https://plato.stanford.edu/entries/logic-combinatory/)</sup>

## Fixed points in typed and practical settings

Because a fixed-point combinator would let one write a non-halting term, it cannot be defined in the simply-typed lambda calculus, whose strong normalization property guarantees every term halts.<sup>[6](https://academicweb.nd.edu/~dchiang/teaching/pl/2025/stlc.html)</sup> Typed languages therefore provide recursion as a primitive instead, for example by adding a fixed-point operator `fix t` to the language, whose evaluation substitutes the function associated with recursion with `fix` over that same function.<sup>[2](https://www.funcp.org/wiki/y-combinator)</sup><sup> • </sup><sup>[14](https://ku-sldg.github.io/plih/types/3-Typed-Recursion.html)</sup> Even with a fixed-point combinator added, the simply-typed calculus still falls short of [Turing completeness](https://www.edgepedia.org/turing-completeness): with `fix`, not every term halts, but it remains decidable whether a given term halts, which is false for Turing machines.<sup>[6](https://academicweb.nd.edu/~dchiang/teaching/pl/2025/stlc.html)</sup>

In Haskell, which is lazy and permits recursive bindings, the fixed-point operator is a library function:<sup>[7](https://hackage-content.haskell.org/package/base-4.11.1.0/docs/Control-Monad-Fix.html)</sup>

```haskell
fix :: (a -> a) -> a
fix f = let x = f x in x
```

`fix f` is the least fixed point of `f`, the least defined `x` such that `f x = x`. Because of Haskell's laziness, `fix f` is not immediately expanded into an infinite sequence of applications, and terminating recursive functions can be written with it, provided `f` indicates when to stop.<sup>[7](https://hackage-content.haskell.org/package/base-4.11.1.0/docs/Control-Monad-Fix.html)</sup><sup> • </sup><sup>[15](https://repository.tudelft.nl/file/File_e5e764ca-7470-4399-a070-c9fd53b1122c)</sup> A factorial can then be written without direct recursion: the helper `factorial f n` calls only its parameter `f`, and `fact = fix factorial` makes it recursive.<sup>[15](https://repository.tudelft.nl/file/File_e5e764ca-7470-4399-a070-c9fd53b1122c)</sup>

**Least fixed points.** The theory of recursive functions connects to least fixed points by ordering partial functions by their domain of definition. Joseph Helfer, in a 2025 arXiv note, proved that Curry's Y produces least fixed points when lambda terms are viewed as partial functions on the set of reduced lambda terms under the natural partial order, answering a question that had apparently not appeared in the literature; the same proof adapts to Turing's Θ.<sup>[3](https://arxiv.org/abs/2504.19379)</sup>

**The population of combinators.** Y is one of infinitely many fixed-point combinators.<sup>[2](https://www.funcp.org/wiki/y-combinator)</sup> Mayer Goldberg of Ben-Gurion University showed in 2005 that the set of fixed-point combinators forms a recursively enumerable subset of a larger set of terms he called non-standard fixed-point combinators, which are observationally equivalent to fixed-point combinators in any computable context but form a set that is not recursively enumerable.<sup>[8](https://tidsskrift.dk/brics/article/view/21867)</sup> Fixed-point combinators also connect to self-replication: the definitions of both Y and Θ apply a combinator to itself, and a fixed-point combinator can be seen as a parameterized version of the self-applying term \( M = \lambda x.xx \), whose self-application \( MM \) reduces to itself like a quine.<sup>[5](https://theory.stanford.edu/~blynn/lambda/quine.html)</sup>

## References

1. [Combinatory Logic, Stanford Encyclopedia of Philosophy](https://plato.stanford.edu/entries/logic-combinatory/)
2. [Y combinator, The Functional Programmer wiki](https://www.funcp.org/wiki/y-combinator)
3. [Joseph Helfer (2025). Y is a least fixed point combinator. arXiv:2504.19379](https://arxiv.org/abs/2504.19379)
4. [Introduction to the Theory of Computation, fixed-point combinators chapter, University of Pennsylvania](https://www.cis.upenn.edu/~cis5110/notes/tcbook-comp.pdf)
5. [Lambda calculus – Quines, Ben Lynn, Stanford University](https://theory.stanford.edu/~blynn/lambda/quine.html)
6. [CSE 40431: Theory of Programming Languages, simply-typed lambda calculus, University of Notre Dame](https://academicweb.nd.edu/~dchiang/teaching/pl/2025/stlc.html)
7. [Control.Monad.Fix, Haskell base library documentation](https://hackage-content.haskell.org/package/base-4.11.1.0/docs/Control-Monad-Fix.html)
8. [Mayer Goldberg (2005). On the Recursive Enumerability of Fixed-Point Combinators. BRICS Report Series 12(1)](https://tidsskrift.dk/brics/article/view/21867)
9. [Fixed-point combinator, nLab](https://ncatlab.org/nlab/show/fixed-point%2Bcombinator)
10. [Lambda Calculus – an overview, ScienceDirect Topics](https://www.sciencedirect.com/topics/computer-science/lambda-calculus)
11. [Theta combinator, PLS Lab](https://www.pls-lab.org/Theta_combinator)
12. [A. M. Turing (1937). The p-function in λ-K-conversion, in Alan Turing: His Work and Impact](https://ndl.ethernet.edu.et/bitstream/123456789/33594/1/80.pdf.pdf)
13. [CS442 Module 2: Untyped λ-calculus, University of Waterloo](https://student.cs.uwaterloo.ca/~cs442/W25/notes/webnotes/Module-2/)
14. [Programming Languages in Haskell: Typed Recursion, Perry Alexander, University of Kansas](https://ku-sldg.github.io/plih/types/3-Typed-Recursion.html)
15. [Fixed-Point (Value) Recursion with Algebraic Effects, TU Delft repository](https://repository.tudelft.nl/file/File_e5e764ca-7470-4399-a070-c9fd53b1122c)

---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics › Formal logic and foundations › Logical calculi and logical syntax › Lambda calculus and type theory › Combinatory logic*

*Initially written Sep 17, 2026 · Reviewed: Sep 30, 2026; Oct 15, 2026 · Edited: Sep 30, 2026; Oct 15, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license