Fixed Points, Part 2: Fixed Behaviors

A fixed point of a function is an input the function maps to itself. When we study the fixed points of a function, we can learn many interesting things about the function itself. This second of four parts talks about the order and degree of a fixed point.

Part 1: What is a fixed point?
Introduces and rigorously defines fixed points. Fixed points are inputs of a function that map to themselves. Knowing the fixed points of a function tells one a lot about that function and how it behaves.
Part 3: Attraction and Orders
If we use the iterative method to find fixed points, we will find some fixed points more often than others. The set of all inputs that lead to a fixed behavior is that behavior’s attraction basin. Attraction basins provide a “map” of the input space that lets us better understand the function itself.
Part 4: Stability
An attractive fixed point is easy to find because many inputs lead to it. This means that if you meant to start with a particular input, but messed up and started with a slightly-incorrect input, you’ll still probably end up with the same output. This captures a “stability” that attractive fixed points. Stability is useful for understanding systems design.

How does one find a fixed point?

Gaiane
I don’t think there can be a general procedure for finding the fixed points of a function!
Plautus
Nonsense! I can think of some simple ways to find fixed points.

To find a fixed point, start at an arbitrary input x₀. Then apply f to get the result x₁; if x₀ = x₁, it is a fixed point; otherwise, repeat with x₁. This is called the “iterative” method for finding fixed points.

Plautus
You must admit that this procedure finds fixed points. In fact, it finds only fixed points!
Gaiane
I’ll agree on the second, but what if there is never an xₖ = xₖ₊₁ in this sequence?
Plautus
I’m not sure that happens…
Gaiane
I’ll show you.

However, the iterative method is not guaranteed to halt. Consider the function f₊ : ℕ→ ℕ defined by:

f₊ 0 = 0
f₊ (S n) = (S (S n))

It’s easy to see that this function has only one fixed point, 0; furthermore, any other input produces a larger output. Since the integers aren’t bounded above, applying f over and over again to any input that isn’t 0 can only lead to an infinite loop.

Gaiane
Your algorithm works well, but it does’t always work.
Plautus
Can’t you look at the function and figure out whether or not it will work, like we did here?
Gaiane
No. There issue is alike to the Halting Problem. I can make a function that has a fixed point if and only if some fixed-point-checker says it doesn’t.
Plautus
But my method works on some functions, right?

When does the iterative method work well?

The iterative method does not work on f₊ because not all inputs iterate to a fixed point. To “fix” this problem, we’ll expand the definition of a fixed point. Previously, a fixed point was an input that mapped to itself; now, we’ll allow a fixed point to be a behavior that maps to itself.

Plautus
Woah, woah, woah. I have many disagreements with that definition.
Gaiane
Do you? I thought it was an intriguing idea.
Plautus
First, fixed points should be points; the name makes that sort-of clear. And second, nowhere is a “behavior” defined.
Gaiane
I guess the name is unfortunate. But if the point is to make the iterative method work, I think we can figure out a reasonable definition of “behavior”.

In this sense, fixed point is some sequence X of inputs

x₀ : x₁ : x₂ : x₃ : ...

such that xᵢ₊₁ = f xᵢ.

Plautus
Well, this definition makes sense, but it is useless.
Gaiane
Useless?
Plautus
Yeah. Of course the iterative method works to find these new “fixed behaviors”. The concept of a behavior just encapsulates the whole principle of iterative search.
Gaiane
Well, sure. It’s not ground-breaking.

If f is applied to X in the sense of being applied to every value in the sequence, the result is just X with the first element removed. We say two behaviors are equal if they have a common suffix, and so we say that a behavior X is a fixed point of f if X = f X.

Plautus
Looks like every function will have a fixed behavior, since we can always use the iterative method to find one.
Gaiane
Yes. That’s why we generalized to behaviors.
Plautus
And sometimes a fixed behavior is really a fixed point. Are there other simple classes?

By on . Share it—it's CC-BY-SA licensed.

Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author and do not necessarily reflect the views of the National Science Foundation.