Kleene's recursion theorem

Remarks

By the smn theorem, there is a total computable $h$ such that $\varphi_{h(u)} = \varphi_{\varphi_u(u)}$ whenever $\varphi_u(u)$ is defined. The composite $f \circ h$ is total computable, so it equals $\varphi_v$ for some $v$. Put $e = h(v)$. Then $\varphi_e = \varphi_{\varphi_v(v)} = \varphi_{f(h(v))} = \varphi_{f(e)}$.

An equivalent form: for every partial computable $\psi(e, x)$ there is $e$ with $\varphi_e(x) \simeq \psi(e, x)$ for all $x$. Here $\simeq$ means that both sides are undefined, or both are defined and equal. Example: with $\psi(e, x) = e$ one gets a program $e$ that outputs its own number on every input, a "quine".

The function $f$ need not have a fixed point $e = f(e)$; the theorem only gives a fixed point of the programs' behaviour. For instance $f(e) = e + 1$ has no fixed point in $\N$, but some $e$ and $e + 1$ compute the same function.

Going deeper

For a student

The recursion theorem justifies definitions in which a program calls itself by index, which is how general recursion is handled inside computability theory. Its proof is a diagonal argument and is closely related to the diagonal lemma used in Gödel's incompleteness theorems. It gives a short proof of Rice's theorem and of the undecidability of the halting problem.