Pavel Panchekha

By

Share under CC-BY-SA.

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.

Fixed Points, Part 2: Fixed Behaviors

Series

This is post 2 of the Fixed Points series.

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 how to find fixed points.

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?