Fixed Points, Part 2: Fixed Behaviors

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?

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?