Difference between revisions of "Fixed-point theorem"
Karl Jones (Talk | contribs) (First) |
Karl Jones (Talk | contribs) |
||
| Line 12: | Line 12: | ||
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. | 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. | ||
| + | |||
| + | (TO DO: organize, cross-ref) | ||
| + | |||
| + | == See also == | ||
| + | |||
| + | * [[Mathematics]] | ||
== External links == | == External links == | ||
* [http://en.wikipedia.org/wiki/Fixed-point_theorem Fixed-point theorem] @ Wikipedia | * [http://en.wikipedia.org/wiki/Fixed-point_theorem Fixed-point theorem] @ Wikipedia | ||
Revision as of 08:21, 6 September 2015
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.
Results of this kind are amongst 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.
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.
(TO DO: organize, cross-ref)
See also
External links
- Fixed-point theorem @ Wikipedia
