Y Combinator

Recursion Without Names

The Y combinator is defined as:

Y = λf.(λx.f(x x))(λx.f(x x))

Its body is two copies of λx.f(x x) -- a variant of the self-application function λx.x x, but with each self-application wrapped in f.

Applied to any function F:

Y F $\to_\beta$ $(\lambda x.F(x\ x))(\lambda x.F(x\ x))$ $\to_\beta$ $F((\lambda x.F(x\ x))(\lambda x.F(x\ x)))$

That second result is F applied to the first result. So:

Y F = F(Y F)

Y finds the fixed point of F. And since F(Y F) = Y F, the term Y F behaves exactly like a recursive definition of F -- without ever naming itself.

Y Definition

The Y combinator is:

Y = λf.(λx.f(x x))(λx.f(x x))

Breaking this down:

• The outer λf. takes a function as input
• The body is an application: two copies of λx.f(x x)
• Each copy is a self-application function (λx.x x) with the self-application wrapped in f

The structure is symmetric: two identical pieces, each containing the pattern "apply x to itself, then hand the result to f." When these two pieces are applied to each other, the self-application regenerates the same structure, and f gets called each time.

Y vs Omega

Compare the structures:

• Omega: (λx.x x)(λx.x x)
• Y body (for a given f): (λx.f(x x))(λx.f(x x))

Omega uses λx.x x -- pure self-application. The argument is applied to itself directly, producing the same term, forever.

Y uses λx.f(x x) -- self-application wrapped in f. The argument is still applied to itself, but the result passes through f first. This gives f the opportunity to use the self-referencing machinery or stop.

Omega is a motor with no load -- it spins freely, doing nothing. Y connects the same motor to f, which puts the energy to work.

Y One Step

Y = λf.(λx.f(x x))(λx.f(x x))

When Y is applied to a function F:

Y F = (λf.(λx.f(x x))(λx.f(x x))) F

The outer λf is applied to F. Beta reduction substitutes F for every f in the body:

Y F $\to_\beta$ (λx.F(x x))(λx.F(x x))

After one step, f has been replaced by the specific function F. What remains is two copies of λx.F(x x) applied to each other -- a self-application structure with F baked in.

Y Two Steps

Following Y F through two beta reduction steps:

Step 1: Y F $\to_\beta$ (λx.F(x x))(λx.F(x x)) (substitute F for f)

Step 2: $\to_\beta$ F((λx.F(x x))(λx.F(x x))) = F(Y F) (the left λx.F(x x) receives the right copy as argument; substituting produces F((λx.F(x x))(λx.F(x x))))

The result of step 2 is F applied to the result of step 1. But the result of step 1 IS Y F (after one step). So:

Y F = F(Y F)

Y F is a fixed point of F. This is the equation that makes recursion possible: F receives Y F as an argument, which is itself a term that reduces to F(Y F), and so on.

Y Property

The defining property of the Y combinator is:

Y F = F(Y F)

This says: applying Y to any function F produces a value that is a fixed point of F. When F is applied to that value, it gets the same value back.

This is what makes recursion work. If F is a "step function" that expects to receive itself as an argument (like the factorial step that needs to call factorial on a smaller input), then Y F gives F exactly what it needs: a term that, when called, invokes F again with the same self-referencing capability.

Why Y Works

Why does Y produce recursion? The mechanism has two parts:

1. Self-application creates copies. The structure (λx.f(x x))(λx.f(x x)) contains self-application: the left half receives the right half and applies it to itself. Each time this happens, the same structure regenerates.

2. f intercepts each cycle. Unlike Omega, where self-application spins freely, Y wraps each x x in f. So each time the structure regenerates, f gets called with the regenerated structure as its argument.

The result: f receives an argument that, when invoked, calls f again with the same kind of argument. An infinite supply of "call me again" tokens, created by self-application and delivered by f's wrapping.

Y for Factorial

The self-reference problem: factorial needs to call itself, but lambda terms are anonymous. The Y combinator solves this.

Define a step function that takes a "self" parameter:

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

This is not recursive -- it does not call itself. It calls whatever function is passed as self. The step function says: "given a function to use for the recursive case, here is how to compute one step of factorial."

Now apply Y:

FACT = Y step

Since Y step = step(Y step), FACT = step(FACT). The step function receives FACT as its self argument -- exactly the function it needs for the recursive call. No naming required.

Channeled Divergence

Omega and Y share the same engine: self-application.

• Omega: (λx.x x)(λx.x x) — self-application with no purpose. Each cycle reproduces the same term. The computation diverges, producing nothing.

• Y F: (λx.F(x x))(λx.F(x x)) — self-application channeled through F. Each cycle calls F, which can do useful work before (optionally) triggering the next cycle.

The insight: divergence is not the enemy. Divergence is an infinite engine. Y takes that engine and connects it to F, turning infinite self-reference into controlled recursion. Whether the recursion terminates depends on F -- if F has a base case (like ISZERO n returning ONE), the chain stops.

The Achievement

The Y combinator achieves something that initially seemed impossible: recursion from anonymous functions.

The problem: lambda terms have no names. A function body cannot refer to the function it belongs to. There is no built-in loop, no def, no let rec.

The solution: Y = λf.(λx.f(x x))(λx.f(x x))

Y uses self-application -- the same mechanism behind Omega's infinite loop -- but channels it through f, giving f a reference to its own computation. No new rules were added. No special syntax. Just lambda terms, applied cleverly.

With Y, any "step function" that takes a self-reference parameter becomes fully recursive. Factorial, Fibonacci, any recursive algorithm -- all expressible in pure lambda calculus.