The combinator (or theta combinator, or Turing's fixed-point combinator) is a way of defining a fixed-point combinator, i.e. a term satisfying the equation
in the untyped -calculus. It is given by
has an additional property over Curry's fixed-point combinator, which is that the equality is witnessed in a single step of -reduction, i.e. .
The combinator was discovered by Alan Turing, and was published in a one-page article in 1937.
Turing, A. M. 1937. ‘The P-Function in λ-K-Conversion’. The Journal of Symbolic Logic 2 (4): 164. https://doi.org/10.2307/2268281.
@article{turing_1937,
title = {The p-{Function} in λ-{K}-{Conversion}},
volume = {2},
doi = {10.2307/2268281},
number = {4},
journal = {The Journal of Symbolic Logic},
author = {Turing, A. M.},
year = {1937},
pages = {164},
}