Fixed point combinator
In computer science, a fixed-point combinator (or fixpoint combinator) is a higher-order function y that satisfies the equation
or in words: y, when applied to an arbitrary function f, yields the same result as f applied to the result of applying y to f. It is so named because, by setting , it represents a solution to the fixed point equation,
A fixed point of a function f is a value that doesn't change under the application of the function f.
Functions that satisfy the equation for y expand as,
A particular implementation of y is Curry's paradoxical combinator Y, represented in lambda calculus by
This combinator may be used in implementing Curry's paradox. The heart of Curry's paradox is that untyped lambda calculus is unsound as a deductive system, and the Y combinator demonstrates that by allowing an anonymous expression to represent zero, or even many values. This is inconsistent in mathematical logic.
Applied to a function with one variable the Y combinator usually does not terminate. More interesting results are obtained by applying the Y combinator to functions of two or more variables. The second variable may be used as a counter, or index. The resulting function behaves like a while or a for loop in an imperative language.
Used in this way the Y combinator implements simple recursion. In the lambda calculus it is not possible to refer to the definition of a function in a function body. Recursion may only be achieved by passing in a function as a parameter. The Y combinator demonstrates this style of programming.
The Y combinator is an implementation of the fixed-point combinator in lambda calculus. Fixed-point combinators may also be easily defined in other functional and imperative languages. The implementation in lambda calculus is more difficult due to limitations in lambda calculus.
...
Wikipedia