Fixed-point theorem
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.
Contents
Description
Results of this kind are among the most generally useful in mathematics.
Fixed-point theorem and programming languages
In denotational semantics of 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
External links
- Fixed-point theorem @ Wikipedia
