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?

  • $\begingroup$ 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) $\endgroup$ – Marzio De Biasi Aug 18 '17 at 18:47
  • $\begingroup$ Yes I think that falls under "recursive scheme" above. $\endgroup$ – Andrej Bauer Aug 18 '17 at 19:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.