Send
Close Add comments:
(status displays here)
Got it! This site "creationpie.com" uses cookies. You consent to this by clicking on "Got it!" or by continuing to use this website. Note: This appears on each machine/browser from which this site is accessed.
Fixed points
1. Fixed points
2. Fixed point puzzle
Consider the following puzzle (origin unknown, found Summer 1991) consisting of a
self-referential sentence.
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.
For example, if you put in 1 for the number of times 1 appears, then 1 now appears 2 times.
This puzzle is a simple constraint logic puzzle.
You are to find a MGU (Most General Unifier) that is a LFP (Least Fixed Point).
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
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. Casti, J. (1996).
Five golden rules: great theories of 20th-century mathematics - and why they matter. New York: John Wiley & Sons., 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.
5. Fixed points in 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.
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. Fixed-point example
Find the fixed point(s) of the following function.
g(x) = x2 + x - 1
That is, find the values of
x such that
g(x) is equal to
x.
So the following holds.
g(x) = x2 + x - 1 = x
Define the following, subtracting
x from both sides in the above equation.
f(x) = g(x)-x = x2 + 1 = 0
Now find values for
x that make
f(x) equal to
0 as you (should have) learned in algebra class in high school.
You were actually finding fixed points, but it is easier for humans to find values that make the function zero (
0) rather then
x.
Solution: The values for
x are
+1 and
-1.
10. Exponential constant
e(0.0) = e0.0 = 1.0000...
e(1.0) = e1.0 = 2.7182...
e(2.0) = e2.0 = 7.3890...
...
|
The exponential constant e, Euler's number, discovered by Jacob Bernoulli in 1683, is defined such that the slope (first derivative) of the function e(x) is e(x) (i.e., as a fixed-point). The value of e = e(1.0) = e1.0 is approximately 2.718281828459.
Numbers such as e are transcendental and, like irrational numbers, have no exact representation and can only be approximated.
|
11. Document fixed point
Whenever 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.
12. 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.
13. Project fixed point
Your goal in a software project is to achieve a fixed point in project development space.
User expectations change, technology changes, etc., so this is practically impossible to do, especially if you wait long enough.
When is the software done?
14. 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)
15. Programming fixed points
Every program (that terminates) determines/calculates a fixed point.
Do you know what is that fixed point? (Dijkstra)
16. Alonzo Church: Lambda calculus
Alonzo Church (1903-1995) was an American logician who invented the
lambda calculus.
E = C | X | ( E | E ) | λ x.E
Alan Turing (1912-1954) developed the ideas that proved the limits of computing before the first programmable digital computer was built.
The
Church-Turing hypothesis forms the basis of the limits of computation.
Turing used an operational definition of a computing machine that become the basis of modern electronic digital computers.
Church used functions and mathematics for a language that became LISP and formed the foundation of modern functional programming languages.
Both systems can compute the same functions (and have the same limitations).
17. Lambda calculus
The lambda calculus is a very simple functional language.
E = C | X | ( E | E ) | λ x.E
An expression
E is one of the following.
A constant C
A variable X
An application of an expression to an expression as ( E . E )
A function as λ x . E (where x is the argument and E the body of the function)
The purpose of a simple language like lambda calculus is that properties of programming languages need only be proved for a few constructs. Such a proof is called a
structural induction proof.
The core
text formatting part of a more general text formatting system is typically a functional
string-rewriting system with abstraction mechanisms to manage redundancy.
18. Combinators
A combinators is a λ expressions with no free variables.
Three combinators (
S,
K and
I.) are sufficient, though not efficient, to express the computation of all computable functions.
| Combinators and reduction rules |
| S apply |
K select |
I identity |
notation |
| S x y z → (x z) (y z) |
K x y → x |
I x → x |
arrow (to/towards) |
| S = λ x y z . ((x z)(y z)) |
K = λ x y . x |
I = λ x . x |
lambda form |
| S = (λ x.(λ y.(λ z .(x z)(y z)))) |
K = (λ x. (λ y. x)) |
I = (λ x. x) |
parenthesized |
19. Fixed point combinator
A
fixed point is a
x for function
f (taking parameter
x) such that
f(x) = x.
Book:
Introduction to combinators and lambda calculus. J. R. Hindley, J F Seldin. 978-0521318396.
A fixed point
combinator, usually called
Y (in lambda calculus, originally by Curry), is a higher order function that takes a function as an argument and returns a fixed point for the argument (if it exists). A
combinator is a closed lambda expression in that it has no free variables. In
lambda calculus terms, the fixed point combinator can be defined as follows.
Y = λ f . ( λ x . f ( x x )) ( λ x . f ( x x ))
If such a fixed point exists, then
Y(f) = f(Y f), and
Y(f) = f(Y f) = f(f(Y(f))), and so on (infinite regression).
A text formatting system that can format itself can model this behavior (to any limit desired).
20. End of page
