show/hide this revision's text 1 [made Community Wiki]

Kleene's recursion theorem says, informally, that when we write a program for a computable function we may assume that the program already has access to its own source code.

More formally, the theorem says that if $f\colon \mathbb{N} \to \mathbb{N}$ is a total computable function (which we view as a method that constructs a program $f(e)$ from a program $e$) there is some program $e_0$ such that the computable function with program $e_0$ is the same function as the function with program $f(e_0)$.

A trivial application: if $f(e)$ is a program that simply outputs $e$ and stops, the program $e_0$ outputs its own source code.

One of the magical applications of the recursion theorem is the lemma on effective transfinite recursion in hyperarithmetical theory, which is one of the key tools in that setting.