Kleene's fixed point theorem

Kleene’s fixed point theorem, also called the recursion theorem, states that every total computable transformation of indices has a fixed point, in the sense that some index and its image compute the same function. Its main use is to build programs that refer to their own index: one may define a program by a description that mentions its own index, and the theorem guarantees that such a program exists. This device is used throughout computability theory, from Rice’s theorem to the constructions of the theory of c.e. degrees.

5.1 The theorem

Theorem 5.1 (Fixed point theorem).#

For every total computable function $f : \nat \to \nat$, there is $e \in \nat$ such that $\Phi_{f(e)} = \Phi_e$.

The equality is between partial functions: $\Phi_{f(e)}(x) \simeq \Phi_e(x)$ for every $x$. In general $f(e) \neq e$; the fixed point is extensional, at the level of the functions computed. A transformation such as $f(e) = e + 1$ has no fixed point in the literal sense, but by the theorem there is an $e$ such that the programs $e$ and $e + 1$ compute the same function.

Proof of Theorem 5.1.

By Corollary 2.3, there is a total computable function $d$ such that for all $n$ and $x$,

$$\Phi_{d(n)}(x) \simeq \Phi_{\Phi_n(n)}(x),$$

where the right-hand side is undefined if $\Phi_n(n)\diverge$: the program $d(n)$, on input $x$, computes $\Phi_n(n)$, and if this halts with value $m$, runs $\Phi_m$ on $x$. The function $f \circ d$ is total computable; let $v$ be an index of it, so that $\Phi_v(n) = f(d(n))$ for every $n$, and $\Phi_v$ is total. Let $e = d(v)$. Then

$$\Phi_e = \Phi_{d(v)} = \Phi_{\Phi_v(v)} = \Phi_{f(d(v))} = \Phi_{f(e)},$$

where the second equality uses $\Phi_v(v)\converge$, which holds since $\Phi_v$ is total.

The proof is a diagonal argument. Consider the table whose row $n$ is the function $\Phi_{\Phi_n(n)}$, the function computed by the program found on the diagonal. The transformation $f$ applied along the diagonal gives the row $v$; so the row $v$ is both $\Phi_{\Phi_v(v)}$, by definition of the table, and $\Phi_{f(d(v))}$, by the choice of $v$. Where Cantor’s argument uses a transformation without fixed point to obtain a contradiction, here every transformation is shown to have a fixed point, as in the reading of the diagonal argument given by Lawvere's fixed point theorem.

Corollary 5.2.#

For every partial computable $g : \nat^2 \rightharpoonup \nat$, there is $e$ such that $\Phi_e(x) \simeq g(e, x)$ for every $x$.

Proof of Corollary 5.2.

By Corollary 2.3, there is a total computable $s$ with $\Phi_{s(n)}(x) \simeq g(n, x)$. By Theorem 5.1, there is $e$ with $\Phi_e = \Phi_{s(e)}$, that is, $\Phi_e(x) \simeq g(e, x)$.

The corollary is the form in which the theorem is used. To build a program with a property, describe its behavior as an algorithm that may use its own index $e$ as a known value; the corollary provides such an $e$. The description must be uniform in $e$, that is, define a partial computable function $g(e, x)$.

Example 5.3.#

1. A program that outputs its own index. With $g(e, x) = e$, there is $e$ such that $\Phi_e(x) = e$ for every $x$. In a programming language, this is a quine, a program that prints its own text.
2. A program halting only on its own index. With $g(e, x) \simeq 0$ if $x = e$ and undefined otherwise, there is $e$ with $W_e = \{ e \}$.
3. Two consecutive indices of the same function. With $f(e) = e + 1$, there is $e$ with $\Phi_e = \Phi_{e+1}$.

Remark 5.4 (Fixed points and paradoxes).#

The corollary allows self-referential definitions that look paradoxical, such as a program $e$ with $\Phi_e(x) \simeq \Phi_e(x) + 1$, obtained from $g(e, x) \simeq \Phi_e(x) + 1$. There is no contradiction: the equation forces $\Phi_e(x)\diverge$ for every $x$, and is then satisfied, both sides being undefined. Partial functions absorb self-reference, as in Proposition 6.6 of “Diagonalization and computation”; the paradoxes of Russell or of the liar would arise only if every program had to produce a value.

5.2 Fixed points with parameters

The fixed point can be found uniformly in a parameter.

Theorem 5.5 (Fixed point theorem with parameters).#

For every total computable $f : \nat^2 \to \nat$, there is a total computable $n : \nat \to \nat$ such that $\Phi_{n(y)} = \Phi_{f(y, n(y))}$ for every $y$.

Proof of Theorem 5.5.

Follow the proof of Theorem 5.1, uniformly in $y$. Let $d$ be as in that proof. By Corollary 2.3 applied to $(y, m) \mapsto f(y, d(m))$, there is a total computable $v$ with $\Phi_{v(y)}(m) = f(y, d(m))$ for all $y$ and $m$. Let $n(y) = d(v(y))$. Since $\Phi_{v(y)}$ is total,

$$\Phi_{n(y)} = \Phi_{d(v(y))} = \Phi_{\Phi_{v(y)}(v(y))} = \Phi_{f(y, d(v(y)))} = \Phi_{f(y, n(y))}.$$

Proposition 5.6.#

Every total computable $f$ has infinitely many fixed points: for every $k$, there is $e \geq k$ with $\Phi_{f(e)} = \Phi_e$.

Proof of Proposition 5.6.

The finitely many functions $\Phi_0, \dots, \Phi_{k-1}$ are not all the partial computable functions, since the constant functions are infinitely many and pairwise distinct, so there is an index $c$ with $\Phi_c \neq \Phi_i$ for every $i < k$. Let $g(x) = c$ for $x < k$ and $g(x) = f(x)$ for $x \geq k$; $g$ is total computable, the finite case distinction being computable. Let $e$ be a fixed point of $g$. If $e < k$, then $\Phi_e = \Phi_{g(e)} = \Phi_c$, contradicting the choice of $c$. So $e \geq k$, and $\Phi_e = \Phi_{g(e)} = \Phi_{f(e)}$.

The proof uses the index $c$ as a fixed number; it need not be found by an algorithm, since only the computability of $g$ matters, and $g$ is computable for every value of the constant $c$.

5.3 Applications

The fixed point theorem gives short proofs of results that otherwise require explicit diagonal constructions. Here is the undecidability of the halting problem again, and a result on the indices of a fixed function.

Proposition 5.7.#

1. The halting set $\emptyset'$ is not computable.
2. For every $a$, the set $\{ e : \Phi_e = \Phi_a \}$ is not computable.

Proof of Proposition 5.7.

1. Suppose $\emptyset'$ is computable. By Corollary 5.2, there is $e$ such that $\Phi_e(x) \simeq 0$ if $e \notin \emptyset'$, and $\Phi_e(x)$ is undefined if $e \in \emptyset'$; the definition is uniform in $e$, since membership in $\emptyset'$ is decided by an algorithm. If $e \in \emptyset'$, then $\Phi_e(e)\diverge$, so $e \notin \emptyset'$; if $e \notin \emptyset'$, then $\Phi_e(e) = 0$, so $e \in \emptyset'$. Both cases are contradictory.
2. Let $P = \{ e : \Phi_e = \Phi_a \}$, suppose it computable, and fix $b$ with $\Phi_b \neq \Phi_a$, for instance an index of a function differing from $\Phi_a$ at $0$. Let $f(x) = b$ if $x \in P$ and $f(x) = a$ otherwise, a total computable function. For a fixed point $e$ of $f$: if $e \in P$ then $\Phi_e = \Phi_{f(e)} = \Phi_b \neq \Phi_a$, so $e \notin P$; if $e \notin P$ then $\Phi_e = \Phi_a$, so $e \in P$.

The second argument works for every set of indices that is closed under equality of the functions computed and is neither empty nor everything. This is Rice’s theorem, the subject of the next lesson.

5.4 Exercises

Exercise 5.8 ★.

Show that there is $e$ such that $\Phi_e(x) = e + x$ for all $x$, and $e$ such that $W_e = \{ 0, 1, \dots, e \}$.

Solution

Apply Corollary 5.2 to $g(e, x) = e + x$, and to $g(e, x) \simeq 0$ if $x \leq e$, undefined otherwise. Both are partial computable functions of $(e, x)$.

Exercise 5.9 ★★.

Show that there is no total computable $f$ such that, for every $e$, the sets $W_{f(e)}$ and $W_e$ differ by exactly one element. Show also that the conclusion of the fixed point theorem cannot be strengthened to $f(e) = e$.

Solution

A fixed point $e$ of $f$ satisfies $\Phi_{f(e)} = \Phi_e$, hence $W_{f(e)} = W_e$, which contradicts the hypothesis. For the second statement, $f(e) = e + 1$ is total computable, and $f(e) \neq e$ for every $e$: the fixed point given by the theorem is extensional only.

Exercise 5.10 ★★★.

An index $e$ is minimal if $\Phi_i \neq \Phi_e$ for every $i < e$. Show that the set of minimal indices contains no infinite c.e. subset.

Hint

Given an infinite c.e. set $A$ of minimal indices, consider the function sending $e$ to an element of $A$ greater than $e$, and apply the fixed point theorem.

Solution

Let $A$ be an infinite c.e. set of minimal indices, and $h$ a total computable function with range $A$. Let $f(e) = h(\mu m\ [h(m) > e])$, a total computable function, since $A$ is infinite; its values lie in $A$ and $f(e) > e$. Let $e$ be a fixed point of $f$. Then $e < f(e)$ and $\Phi_e = \Phi_{f(e)}$, so $f(e)$ is not minimal, although it belongs to $A$.

5.5 Notes and references

The fixed point theorem was proved by Kleene in 1938, in a paper on notations for ordinals, where it is used to define functions by effective transfinite recursion. Rogers formulated the version for transformations of indices given here. The result on minimal indices is usually attributed to Blum (1967), in a paper on the size of programs. Moschovakis gives a survey of the many uses of the theorem.

• S. C. Kleene, On notation for ordinal numbers, Journal of Symbolic Logic 3 (1938), 150–155.
• H. Rogers, Theory of Recursive Functions and Effective Computability, McGraw-Hill, 1967.
• M. Blum, On the size of machines, Information and Control 11 (1967), 257–265.
• Y. N. Moschovakis, Kleene’s amazing second recursion theorem, Bulletin of Symbolic Logic 16 (2010), 189–239.