Send
Close Add comments:
(status displays here)
Got it! This site uses cookies. You consent to this by clicking on "Got it!" or by continuing to use this website.nbsp; Note: This appears on each machine/browser from which this site is accessed.
Fixed points
1. Fixed points
2. Puzzle
Consider the following puzzle (origin unknown).
In this sentence, the number of occurrences
of 0 is ________,
of 1 is ________,
of 2 is ________,
of 3 is ________,
of 4 is ________,
of 5 is ________,
of 6 is ________,
of 7 is ________,
of 8 is ________, and
of 9 is ________.
Fill in the blanks with the appropriate numbers so that the sentence is true. Exercise: How does this puzzle relate to fixed-point semantics?
3. Fixed points
A
mathematical fixed-point is a value of
x in
f(x) where
f(x) =
x.
f(x) = x
g(x) = f(x) - x = 0
This is why finding the values of
x for which
g(x) is
0 is so important.
4. Brouwer fixed point theorem
5. Brouwer fixed point theorem
Suppose that X is a topological space that is both compact and convex, and let f be a continuous map of X to itself. Then f has a fixed point in X, that is, there exists a point x* in X such that f(x*) = x. Casti96, p. 71.
In terms of a simple specific example, every continuous curve that starts at
x equal to
0.0 and ends at
x equal to
1.0 must cross the straight diagonal line defined by
f(x) = x
at least once. The intersection(s) of the continuous curve with the diagonal line is the fixed point solution.
The Brouwer fixed point theorem is a powerful way to show that solutions do, in fact, exist for certain classes of problems.
6. Economics
In 1932, mathematician John von Neumann presented a talk, later published in 1938, in which he generalized the Brouwer fixed point theorem in order to transform the field of economics from a static theory to a dynamic theory. Many economists have since added to that work in order to show how economies can exhibit cyclic and chaotic behavior.
7. Fixed points
A fixed-point of a function f is an object x such that
f(x) = x
Have you ever learned to compute or determine a fixed point?
8. Quadratic formula
f(x) = x2 + 3*x + 1
Then, a fixed point of
f is when
f(x) = x
or, expending the definition of
f,
x2 + 3*x + 1 = x
and, subtracting
x from both sides,
x2 + 2*x + 1 = 0
which can be solved using the quadratic formula. Thus solving for
x is equivalent to finding the fixed point solutions.
9. Document fixed point
When you write a paper, you are trying to achieve a fixed point in paper writing space. That is, you want to write a paper such that when you proof the entire paper, there are not changes to be made.
You paper is done either,
when you reach a fixed point in paper writing space,
or you give up and turn in what you have.
10. Programming example
Programming example: Write a program that has as its output an exact copy of its source code.
This is a fixed point in program writing space.
11. Project fixed point
Your goal in a software project is to achieve a fixed point in project development space.
But, user expectations change, technology changes, etc., so this is practically impossible to do, especially if you wait long enough.
When is the software done?
12. Minimum force principle
The minimum force needed to accomplish an action (finite resources and opportunity costs) should be used.
Least-fixed point theory (denotational semantics of programming languages)
Most-general unifier (Logic programming theory)
13. Programming fixed points
Every program (that terminates) determines/calculates a fixed point.
Do you know what is that fixed point? (Dijkstra)
14. End of page
