Proof of the Recursion Theorem

The recursion theorem (Kleene's fixed-point theorem) is a fundamental result guaranteeing that self-referential programs exist. It states that for any computable transformation of programs, there is a fixed point — a program that computes the same function as its own transformation.

Statement

Theorem5.3Kleene's Recursion Theorem

For every total computable function $f: \mathbb{N} \to \mathbb{N}$ , there exists $n \in \mathbb{N}$ such that $\varphi_n = \varphi_{f(n)}$ , where $\varphi_e$ denotes the partial function computed by the $e$ -th Turing machine.

Proof

By the $s$ - $m$ - $n$ theorem, there is a total computable function $s$ such that $\varphi_{s(x,y)}(z) = \varphi_x(\langle y, z \rangle)$ for all $x, y, z$ .

Define a total computable function $d$ by $d(x) = s(x, x)$ . Then $\varphi_{d(x)}(z) = \varphi_x(\langle x, z \rangle)$ .

Now, given the total computable function $f$ , define a computable function $h$ by $h(\langle y, z \rangle) = \varphi_{f(d(y))}(z)$ . Let $e$ be an index for $h$ , so $\varphi_e(\langle y, z \rangle) = \varphi_{f(d(y))}(z)$ .

Set $n = d(e)$ . Then: $\varphi_n(z) = \varphi_{d(e)}(z) = \varphi_e(\langle e, z \rangle) = \varphi_{f(d(e))}(z) = \varphi_{f(n)}(z).$

Thus $\varphi_n = \varphi_{f(n)}$ . $\square$

■

Applications

ExampleSelf-Printing Programs (Quines)

A quine is a program that outputs its own source code. The recursion theorem guarantees their existence: let $f$ be any total computable function (e.g., $f(e)$ = index of the machine that prints $e$ ). The fixed point $n$ with $\varphi_n = \varphi_{f(n)}$ is a program that prints its own index.

RemarkAlternative Proof of Halting Problem

The recursion theorem gives an elegant alternative proof that the halting problem is undecidable. Suppose $H$ decides $K = \{e : \varphi_e(e) \downarrow\}$ . Define $f(e) =$ index of the machine that on all inputs does the opposite of what $H$ predicts about $e$ . By the recursion theorem, there exists $n$ with $\varphi_n = \varphi_{f(n)}$ , leading to $n \in K \iff n \notin K$ .

ExampleMyhill's Isomorphism Theorem

Two sets are recursively isomorphic (there is a computable bijection $f: \mathbb{N} \to \mathbb{N}$ with $f(A) = B$ ) if and only if they are many-one equivalent ( $A \leq_m B$ and $B \leq_m A$ ). The proof of the forward direction of this uses the recursion theorem to construct the isomorphism by a back-and-forth argument.