Difference between revisions of "Fixed-point theorem"

Revision as of 16:06, 29 November 2016

In mathematics, a fixed-point theorem is a result saying that a function F will have at least one fixed point (a point x for which F(x) = x), under some conditions on F that can be stated in general terms.

Description

Results of this kind are among the most generally useful in mathematics.

Fixed-point theorem and programming languages

In denotational semantics programming languages, a special case of the Knaster–Tarski theorem is used to establish the semantics of recursive definitions.

While the fixed-point theorem is applied to the "same" function (from a logical point of view), the development of the theory is quite different.

The same definition of recursive function can be given, in computability theory, by applying Kleene's recursion theorem.

These results are not equivalent theorems; the Knaster–Tarski theorem is a much stronger result than what is used in denotational semantics.

Church–Turing thesis

However, in light of the Church–Turing thesis their intuitive meaning is the same: a recursive function can be described as the least fixed point of a certain functional, mapping functions to functions.

See also

• Denotational semantics
• Function (mathematics)
• Mathematics
• Recursion
• Recursive function

External links

• Fixed-point theorem @ Wikipedia