# What are considered to be the most canonical and important consequences of the recursion theorem?

The recursion theorem in computability states that, for any computable map $f : \mathbb{N} \to \mathbb{N}$ there exists $n \in \mathbb{N}$ such that $\varphi_{f(n)} = \varphi_n$, where $\varphi$ is a standard enumeration of partial computable functions. The one given here is due to Rogers, there is another by Kleene (but they can be derived from each other).

I am collecting typical uses of recursion theorem. I can think of the following:

• existence of quines, for instance that there is $k \in \mathbb{N} \to \mathbb{N}$ such that $\phi_k = \lambda n . k$, or that there is $n$ such that $W_n = \{n\}$, where $W$ is a standard enumeration of c.e. sets.

• it can be used to establish validity of various kinds of recursion schemata for defining computable functions,

• the Kreisel-Lacombe-Shoenfield-Tseitin theorem stating that "all computable functionals are continuous".

What are some other typical uses of recursion theorem?

• It "allows" self-reference of TMs and can be used to easily prove a bunch of undecidability/recognizability results ... see for example these slides (e.g. $MIN_{TM}$ is not Turing recognizable) – Marzio De Biasi Aug 18 '17 at 18:47
• Yes I think that falls under "recursive scheme" above. – Andrej Bauer Aug 18 '17 at 19:22