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
Another common fixed point combinator is the Turing fixed-point combinator (named for its discoverer Alan Turing):
This combinator is of interest because a variation of it can be used with applicative-order reduction[?]:
Fixed point combinators are not especially rare. Here is one constructed by Jan Willem Klop[?]:
where
See also: combinator, combinatory logic, lambda calculus.
Search Encyclopedia
|
Featured Article
|