Encyclopedia > Fixed point combinator

  Article Content

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[?]:

Yk = (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)


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.

All Wikipedia text is available under the terms of the GNU Free Documentation License

  Search Encyclopedia

Search over one million articles, find something about almost anything!
  Featured Article
Tiananmen incident

... Zedong's wife. Mourning for Zhou was limited by directives of the Communist Party of China, the flag, for example, being lowered to half-staff for only one hour. April 4 ...