TheInfoList

In mathematics and computer science in general, a fixed point of a function is a value that is mapped to itself by the function. In combinatory logic for computer science, a fixed-point combinator (or fixpoint combinator)[1]:page 26 is a higher-order function ${\displaystyle {\textsf {fix}}}$ that returns some fixed point of its argument function, if one exists.

Formally, if the function f has one or more fixed points, then

${\displaystyle {\textsf {fix}}\ f=f\ ({\textsf {fix}}\ f)\ ,}$

and hence, by repeated application,

${\displaystyle {\textsf {fix}}\ f=f\ (f\ (\ldots f\ ({\textsf {fix}}\ f)\ldots ))\ .}$

General information

Because fixed-point combinators can be used to implement recursion, it is possible to use them to describe specific types of recursive computations, such as those in fixed-point iteration, iterative methods, recursive join in relational databases, data-flow analysis, FIRST and FOLLOW sets of non-terminals in a context-free grammar, transitive closure, and other types of closure operations.

A function for which every input is a fixed point is called an A function for which every input is a fixed point is called an identity function. Formally:

In contrast to universal quantification over all ${\displaystyle x}$, a fixed-point combinator constructs one value that is a fixed point of ${\displaystyle f}$. The remarkable property of a fixed-point combinator is that it constructs a fixed point for an arbitrary given function ${\displaystyle f}$.

Other functions have the special property that, after being applied once, further applications don't have any effect. More formally:

${\displaystyle \forall x(f\ (f\ x)=f\ x)}Other functions have the special property that, after being applied once, further applications don't have any effect. More formally:$

Such functions are called idempotent (see also projection). An example of such a function is the function that returns 0 for all even integers, and 1 for all odd integers.

In lambda calculus, from a computational point of view, applying a fixed-point combinator to an identity function or an idempotent function typically results in non-terminating computation. For example, we obtain