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 wellknown fixed point combinator, discovered by Haskell B. Curry, is
Another common fixed point combinator is the Turing fixedpoint combinator (named for its discoverer Alan Turing):
This combinator is of interest because a variation of it can be used with applicativeorder 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
