# 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 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?