What is fixed point?

Question

I'm rewatching some of the earlier lectures on SICP. The notion of a fixed-point is a bit confusing to me. The fixed-point procedure: should I be thinking about it this way, "it's the way to find a fixed-point of a given function." So given f(2) = 2?

Also why is it stated in this lecture, that a new function y that maps to x / y is a fixed point?

Answer 1

According to Fixed point (mathematics) on Wikipedia:

In mathematics, a fixed point (sometimes shortened to fixpoint, also known as an invariant point) of a function is an element of the function's domain that is mapped to itself by the function.

So as you wrote, f(2) = 2 indicates that 2 is a a fixed point of f.

Answer 2

Just Ethier's answer addresses what a fixed point is, but this still leaves the other part of your question:

Also why is a new function y that maps to x / y a fixed point?

The lecturer is speaking quickly at the point that you mentioned, but I think that he's actually saying that √x is the fixed point of more than one function, and that an obvious function of which √x is a fixed point is

    y ↦ x / y

since

    √x = x / √x

However, the given procedure for calculating fixed points would not work for this function, because its internal procedure iter loops on an initial value and the function applied to the initial value. Thus the sequence of new/old values is (1,2), (2,1), (1,2), …

Answer 3

It's when you get the same result as the last time in an iterated function. To grasp that imagine a normal function for a known sequence:

Imagine the function f(x) = 2^(n+1)-1. It's called the Mersenne sequence and you are to supposed to feed it an index from 0 and it makes the sequence 1, 3, 7, 15, 31, ... (basically it's one less than every power of 2)

Now you can make the same sequence by making changing the function to be iterative. The iterative version is f(x) = 2x + 1. Now x is not going to be index anymore but the previous result. You start at 0 and get 1, 3, 7, 15, 31, ...

Now this function doesn't have fixed point because the result from applying it is always larger than it's argument. We can say it blows up.

To answer your first question. In the SICP video they are talking about square root. Square root of n is the fixed point of the iterated function f(x) = n/x because sqrt(x^2) = x It does not map to other functions.

A general fixed point function would be like their definition of fixed-point and that is that you iterate a function until the value you feed into the function is equal (or close enough) to the next calculated number.

Now we see that we couldn't find a fixed point from Mersenne and we know we need to average damp n/x for it to converge but some functions actually converge on their own, like f(x) = x/4 + 1 converge to 3/2. Notice that even if you were to average dampt it it will still become 3/2 so only the functions without fixed point will loop forever.

Answer 4

Here's my two cents. It can indeed be confusing.

First, simple definition: a point x is "fixed point" of a function f, if f(x) == x.

To put it the other way around, x = f(x).

Can the above have any sense? Seems unlikely. It uses the value being defined, after all.

x is not necessarily a simple number though. It can be a function, or a lazy infinite list, and f can have an effect of partially defining it. Then, by repeated evaluation of

x = f(x) = f( f(x)) = f( f( f(x))) = f( f( f( f(x)))) = ....

the value is being defined more and more. Now this does remind us of the numeric example of calculating the fixed point of f(y) = (y + n/y)/2 through iterated calculation,

n=25; f(1.0)=13.0; f(13.0)=7.4615383; f(7.4615383)=5.406027;
      f(5.406027)=5.0152473, f(5.0152473)=5.0152473; f(5.0152473)=5.0

The crucial part is not to wait until the infinite chain of evaluations is over (it never is), but to have a lazy list recording the progression of evaluation steps. Then, our value the infinite list is being progressively defined: first it is undefined at all; then its first (head) element is defined and the rest still isn't; then its two first elements are defined; etc. etc. : [1.0,13.0,7.4615383,5.406027,5.0152473,5.000023,5.0,5.0,5.0 ...].

And just as the numeric values are converging to some number, becoming closer and closer to the "final" value (which is never quite reached, but the distance gets smaller and smaller), so is the infinite list of results converging to its ultimate value, the fully-defined infinite list with all its elements defined (quite an impossible feat, of course), getting closer and closer in definedness to that ultimate value (saying it simply, having its elements defined one by one, but mathematicians like it complicated).

Similarly with functions. If g(h,n) = n<2 -> 1 ; else -> n*h(h,n-1) then g(error) is a (curried) function of one argument defined only for n < 2, as for any other argument it will diverge (cause an error). But g( g(error)) is defined for all n < 3; g( g( g(error))) - for all n < 4, etc. Again we have a progression of values being more and more defined... And so the limit of that progression, the "ultimate value", the fixed point of the function g is such a function f that f = g(f) which is defined for any n, however big. Which coincidentally, is a factorial function, defined without the use of recursion.