Fixed Points

What Is a Fixed Point

A fixed point of a function F is a value X such that:

F X = X

The function maps X back to itself. X is "fixed" -- it does not move under F.

A simple example from ordinary math: the function f(x) = x has every number as a fixed point, because f(x) = x for all x.

A more interesting example: $f(x) = x^2$ has two fixed points, $x = 0$ and $x = 1$, because $0^2 = 0$ and $1^2 = 1$.

In lambda calculus, fixed points become the tool that makes recursion possible without self-reference.

Fixed Points in Math

Fixed points are familiar from ordinary mathematics. Consider $f(x) = x^2$. Which values does $f$ leave unchanged?

• $f(0) = 0^2 = 0$. So 0 is a fixed point.
• $f(1) = 1^2 = 1$. So 1 is a fixed point.
• $f(2) = 2^2 = 4 \neq 2$. So 2 is NOT a fixed point.

Not every function has fixed points in ordinary math. The function f(x) = x + 1 has none -- no real number satisfies x + 1 = x.

Some functions have exactly one, some have two, some have infinitely many. The identity function f(x) = x has every value as a fixed point.

Every Term Has One

In ordinary math, many functions have no fixed points at all. f(x) = x + 1 has none. f(x) = -x has only x = 0.

In lambda calculus, something remarkable is true:

Every lambda term F has at least one fixed point.

That is: for any F, there exists some X such that F X = X.

This is the fixed point theorem of lambda calculus. It holds because lambda calculus allows self-application -- terms can be applied to copies of themselves -- and this creates enough "room" for fixed points to always exist.

We will soon see how to construct these fixed points explicitly.

Why Remarkable

Why is the fixed point theorem so remarkable?

In ordinary mathematics, fixed points are the exception, not the rule. Consider these functions on real numbers:

• f(x) = x + 1 -- no fixed points
• f(x) = 2x -- one fixed point (x = 0)
• $f(x) = x^2$ -- two fixed points ($x = 0$, $x = 1$)
• f(x) = x -- infinitely many (every number)

Most functions do not have them. You have to get lucky, or look at special classes of functions.

But in lambda calculus, the fixed point theorem guarantees that every function has at least one. No exceptions. Not even functions that "look like" they should have none. This is a deep structural property of the system.

Fixed Point of Identity

Consider the identity function:

I = λx.x

A fixed point of I is any X where I X = X. But I X = X for every term X -- that is what the identity does. It returns its argument unchanged.

So the identity function has infinitely many fixed points: every lambda term is a fixed point of I.

At the other extreme, consider a function like the SUCC function on Church numerals. SUCC has exactly one fixed point -- not obvious to find, but guaranteed to exist by the fixed point theorem.

Connection to Recursion

Here is why fixed points matter for recursion.

Suppose we want a factorial function FACT. We can describe what FACT should do using a "step" function:

step = λf.λn. IF (ISZERO n) ONE (MUL n (f (PRED n)))

This step function takes a function f and returns an improved version: one that handles n = 0 directly, and delegates to f for smaller values.

Now, if FACT is a fixed point of step, then:

step FACT = FACT

This means FACT already IS the improved version of itself. It handles n = 0 and delegates to... itself. That is recursion.

A fixed point of the step function is the recursive function we wanted.

The Step Function

Look at the step function for factorial again:

step = λf.λn. IF (ISZERO n) ONE (MUL n (f (PRED n)))

The parameter f is a placeholder for "the function to call recursively." The step function does not know what f is -- it just uses it when it needs to handle smaller values.

• When n = 0: return ONE (base case, f not needed)
• When n > 0: return MUL n (f (PRED n)) (recursive case, calls f)

The step function describes one layer of computation. It handles n directly if it can, and delegates to f otherwise.

The question is: what should f be? If we could somehow pass the completed factorial as f, the step function would produce... the completed factorial. That is exactly a fixed point.

step Applied to FACT

Let us make the connection explicit.

We want a function FACT such that for any n:

FACT n = IF (ISZERO n) ONE (MUL n (FACT (PRED n)))

We define the step function:

step = λf.λn. IF (ISZERO n) ONE (MUL n (f (PRED n)))

If step FACT = FACT, we can expand the left side:

step FACT = λn. IF (ISZERO n) ONE (MUL n (FACT (PRED n)))

And since this equals FACT, we get:

FACT = λn. IF (ISZERO n) ONE (MUL n (FACT (PRED n)))

That is exactly the recursive definition of factorial. The fixed point equation step FACT = FACT is the recursive definition, written differently.

Finding Fixed Points

We now know what we need: given any step function F, find its fixed point X such that F X = X.

The fixed point theorem guarantees X exists. But we need a way to construct it.

What we want is a combinator Y -- a single lambda term -- such that for any function F:

Y F = F (Y F)

Why does this work? If we let X = Y F, then:

X = Y F = F (Y F) = F X

So X = F X, which means X is a fixed point of F.

The combinator Y takes any function and produces its fixed point. Such a term is called a fixed-point combinator.

We have not yet built Y. But we know exactly what it must satisfy: Y F = F (Y F) for all F.

Fixed-Point Combinator

A fixed-point combinator is any lambda term Y satisfying:

Y F = F (Y F) for all F

The key insight: if X = Y F, then X = F X. The result of applying Y to any function F is a fixed point of F.

This is all we need for recursion:

• Write a step function that describes one layer of your recursive computation
• Apply Y to it
• The result is the complete recursive function

Y step = step (Y step) = step (step (Y step)) = ...

Each "unfolding" of Y step applies one more layer of step. The computation proceeds as deep as needed.

We have not yet seen how to build Y. That is the next concept. For now, the important thing is the specification: Y F = F (Y F).