Fixed point combinator

A fixed point combinator is a function which computes fixed points of other functions. A 'fixed point' of a function is a value left 'fixed' by that function; for example, 0 and 1 are fixed points of the squaring function.

In certain formalizations of mathematics, such as the lambda calculus and combinatorial calculus, every function has a fixed point. In these formalizations, it is possible to produce a function, often denoted Y, which computes a fixed point of any function it is given. Since a fixed point x of a function f is a value that has the property f(x) = x, a fixed point combinator Y is a function with the property that f(Y(f)) = Y(f) for all functions f.

One well-known fixed point combinator, discovered by Haskell B. Curry, is

Y = λf.(λx.(f (x x)) λx.(f (x x)))

Another common fixed point combinator is the Turing fixed-point combinator (named for its discoverer Alan Turing):

Θ = (λx.λy.(y (x x y)) λx.λy.(y (x x y)))

This combinator is of interest because a variation of it can be used with applicative-order reduction[?]:

Θ_v = λh.(λx.(h λy.(y (x x y))) λx.(h λy.(y (x x y))))

Fixed point combinators are not especially rare. Here is one constructed by Jan Willem Klop[?]:

Y_k = (L L L L L L L L L L L L L L L L L L L L L L L L L L L L)

where

L = λabcdefghijklmnopqstuvwxyzr.(r (t h i s i s a f i x e d p o i n t c o m b i n a t o r))

See also: combinator, combinatory logic, lambda calculus.