---
tag: F3Z30M606H
kind: statement
role: theorem
name: Kleene's recursion theorem
msc: [03D20]
uses: [KZSB5E471K, MFJXPAF0R0]
about: [KZSB5E471K]
sources:
  - url: https://en.wikipedia.org/wiki/Kleene's_recursion_theorem
same_as:
  wikidata: Q1933521
  wikipedia: Kleene's recursion theorem
---

## Statement

Fix a standard [[Gödel numbering|MFJXPAF0R0]] of programs, and let $\varphi_e$ be the partial [[computable function|KZSB5E471K]] of one argument computed by program $e$.
Let $f \colon \N \to \N$ be a total computable function.
Then there is $e \in \N$ such that $\varphi_e = \varphi_{f(e)}$ as partial functions.

## Remarks

By the [[smn theorem|YWX4FCFPAP]], 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.

## Explanations

### L1 human

The theorem says that a program may refer to its own code.
Any mechanical transformation of programs leaves the behaviour of at least one program unchanged.
A classic consequence is that there are programs that print their own source code.

### L2 human

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|X9WYNYE29C]].
It gives a short proof of [[Rice's theorem|AKDR5YBBE2]] and of the undecidability of the [[halting problem|Z7TN2B35B0]].