Three Fixed Points Hiding in "Recursive Self-Improvement"

I recently gave a talk at a reading group on self-reference and AI. The announced topic was recursive self-improvement (RSI), but most of my time went to a narrower question: when we say a system “refers to itself,” what exactly is being referred to, and what machinery makes that possible?

This post is the first half of that talk, the background. Part 2 applies it to language models.

Where this started: prompt(prompt)

A higher-order function takes a function and returns a function:

People building LLM systems now write the same shape with prompts. A meta-prompt takes a prompt, together with the result of running it, and returns a better prompt:

In both cases, something that is normally executed becomes something that can also be passed around, inspected, and transformed. Lisp programmers call this code-as-data:

(+ 1 2)     ; code: evaluate it, get 3
'(+ 1 2)    ; data: keep the expression itself

For functions, we know what happens when you close the loop and feed a function to itself: you get recursion, and the Y combinator is the classical way to build it. For prompts I did not have an equally crisp answer, and that is what sent me back to the theory.

The shape of recursive self-improvement

Ordinary improvement looks like this:

$S$ is the state of the system (weights, code, memory, tool configuration) and $I$ is one improvement step, chosen by someone outside the system: an engineer, an optimizer, a training script.

Recursive self-improvement asks for more. The improvement step is itself read off the current state:

$S_t$ appears twice: once as the thing that produces the rule, and once as the thing the rule is applied to. This is the same shape as the λ-term $\lambda f.\, f\, f$, which takes a function and applies it to itself.

Equations of this shape invite the phrase “fixed point.” The trouble is that at least three different mathematical objects go by that name, and they answer different questions.

Fixed point one: a program that has its own description

Here is a Python quine, a program that prints its own source:

s='s=%r;print(s%%s)';print(s%s)

Quines are not a trick of Python. They exist in every reasonable programming language because of Kleene’s second recursion theorem: for every total computable transformation $F$ on program codes, there is a program $e$ such that

In words: whatever you plan to do to a program’s text, some program already behaves as if that had been done to its own text. The practical corollary is that any program can be written as though it had access to its own description and could compute with it. A quine is the special case where the computation is “print it.”

Two features of this theorem matter later.

First, it is about descriptions. The thing being referred to is the code $e$, the text of the program. I will call this representational self-access.

Second, the proof is a construction. The s-m-n theorem builds $e$ explicitly, once. Nothing is run until it converges. A quine does not approximate its source over many rounds; it prints it in a single execution.

Fixed point two: a function defined in terms of itself

The λ-calculus has three kinds of expressions (variables, abstractions $\lambda x.\, e$, and applications $e_1\, e_2$) and one rule of computation, β-reduction:

There are no names. That creates a problem for recursion. In Python, fact can call fact because the body can mention the name. An anonymous function has nothing to call:

The way out takes three steps.

Step 1: turn the recursive call into a parameter. Define a one-step operator that is not itself recursive:

$G$ says: give me something that handles smaller inputs, and I will handle one more step. Nowhere does $G$ call $G$.

Step 2: ask for a fixed point of $G$. If some $f$ satisfies $f = G(f)$, then substituting the definition of $G$ gives

which is the recursive definition we wanted.

Step 3: build the fixed point. The Y combinator is

and for any $g$ it satisfies $Y g = g\,(Y g)$. So $\mathit{fact} \triangleq Y\, G$. Running it peels off one layer of $G$ per reduction:

and each layer performs one multiplication: $\mathit{fact}(3) \to 3 \cdot \mathit{fact}(2) \to 3 \cdot 2 \cdot \mathit{fact}(1) \to \cdots \to 6$.

The engine is the self-application $x\, x$ inside $Y$: two identical copies of $\lambda x.\, f\,(x\,x)$, one fed to the other.

What this shows is that inside the pure λ-calculus, using only abstraction and application, recursion can be constructed. The language does not need to supply a rec primitive, function names, mutable state, or a call stack.

It is also a different kind of self-reference from the quine. $Y$ never gives a function its own source code. It gives the function itself, as a value to call. I will call this behavioral self-reference. Its theoretical counterpart is Kleene’s first recursion theorem: every computable functional $\Phi$ on partial functions has a least fixed point $g$ with $\Phi(g) = g$. This is the semantic basis of recursive definitions, and in Scott’s denotational semantics $Y$ is interpreted as exactly the least-fixed-point operator.

So Kleene’s two theorems split along a line that is easy to miss. The first works at the level of functions (extensional): what the program computes. The second works at the level of descriptions (intensional): what the program’s text is.

Fixed point three: where an iteration settles

Start from $x_0 = 1$ and repeatedly press the cosine key on a calculator:

The limit satisfies $x^* = \cos(x^*)$. Notice the two roles here. The fixed point is defined by the equation. The iteration is one method for finding it.

These are two different statements:

• Algebraic: does $x^* = f(x^*)$ have a solution?
• Dynamical: does $x_{t+1} = f(x_t)$, started from a given $x_0$, converge to it?

The Banach fixed-point theorem connects them under an extra condition: a contraction mapping has a unique fixed point, and iteration from any starting point converges to it. Cosine is a contraction on $[0, 1]$ because $|\cos'(x)| = |\sin x| \lt 1$ there. Without the condition, the two statements come apart. Take $f(x) = 2x$. Zero is a fixed point, but starting from $x_0 = 1$ the iteration goes $1 \to 2 \to 4 \to 8 \to \cdots$ and never gets there.

Keeping them apart

Now go back to $S_{t+1} = \Phi(S_t)(S_t)$. There are two separate things to ask about it.

1. Can $\Phi$ be written down at all? Does the system have the means to refer to, describe, and rewrite itself? This is a definitional question, and Kleene’s theorems and the Y combinator speak to it.
2. What happens when it runs? After $\Phi$ has acted many times, does $S_t$ stabilize, diverge, oscillate, or park at some equilibrium? This is a question about the whole trajectory, and it is the Banach-style question.

An answer to one does not transfer to the other. A system can have perfect access to its own description and a trajectory that goes nowhere useful. And a system can have a beautifully convergent iteration with no self-reference in it at all: cosine does not know it is cosine.

My own view, after working through this, is that the first question is the easier of the two. In part 2 I look at what each one says about language models.