<p>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).</p>

<p>I am collecting typical uses of recursion theorem. I can think of the following:</p>

<ul>
<li><p>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.</p></li>
<li><p>it can be used to establish validity of various kinds of recursion schemata for defining computable functions,</p></li>
<li><p>the Kreisel-Lacombe-Shoenfield-Tseitin theorem stating that "all computable functionals are continuous".</p></li>
</ul>

<p>What are some other typical uses of recursion theorem?</p>

CC BY-SA 3.0
2017-08-18T18:47:13.263Z
It "allows" self-reference of TMs and can be used to easily prove a bunch of undecidability/recognizability results ... see for example [these slides](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-045j-automata-computability-and-complexity-spring-2011/lecture-notes/MIT6_045JS11_lec10.pdf) (e.g. $MIN_{TM}$ is not Turing recognizable)
Marzio De Biasi
CC BY-SA 3.0
2017-08-18T19:22:53.847Z
Yes I think that falls under "recursive scheme" above.
Andrej Bauer
CC BY-SA 4.0
2023-10-29T17:17:54.127Z
See Moschovakis' paper *Kleene's Amazing Second Recursion Theorem* for a host of other applications. (here is the extended abstract https://www.math.ucla.edu/~ynm/papers/ynmcsl2009.pdf).
Siddharth
<computability><recursion>
What are considered to be the most canonical and important consequences of the recursion theorem?
Andrej Bauer
# What are considered to be the most canonical and important consequences of the recursion theorem?

(Asked by: username_0 on 2017-08-17)

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?

**Tags:** computability, recursion

> **Comments:**
> **username_1**: It "allows" self-reference of TMs and can be used to easily prove a bunch of undecidability/recognizability results ... see for example [these slides](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-045j-automata-computability-and-complexity-spring-2011/lecture-notes/MIT6_045JS11_lec10.pdf) (e.g. $MIN_{TM}$ is not Turing recognizable)  
> **username_0**: Yes I think that falls under "recursive scheme" above.  
> **username_2**: See Moschovakis' paper *Kleene's Amazing Second Recursion Theorem* for a host of other applications. (here is the extended abstract https://www.math.ucla.edu/~ynm/papers/ynmcsl2009.pdf).  

---

## 0 answers

