Two of the most important and fundamental results in computability are those by Stephen Kleene — the so called “recursion theorems” — which were first proved by Kleene himself in 1938. They have profound consequences in the whole field of computability; probably, the two most famous applications are to generate quines and construct fixed points.

A couple of notes about the notation used:

- $\text{TM}$ denotes a Turing Machine;
- $\downarrow$ denotes the termination of a function (program).

## 1º Recursion Theorem

Following is what the first recursion theorem states.
Let
$t$ be a *total, recursive function*.

That is also known as the **fixed-point** theorem, since it proves there’s a fixed point — namely,
$e$.

### Proof

Let’s define:

By applying **s-m-n** theorem (again, be Kleene) it is possible to fix the first parameter —
$u$ —, thus building a new function which only takes one variable (
$x$).
The function thus obtained is
$\varphi_{g(Q, u)}(x)$.

We know, from the premise, that $t$ is total and recursive. Function $g$ is total recursive as well, thanks to s-m-n theorem. This implies that $t \circ g$ is also recursive.

This implies that
$\exist v \text{ TM} : \varphi_{v}(u) = t(g(Q, u))$.
By substituting
$u$ (which is a generic **Turing Machine**, *TM*) with
$v$ (which is a specific TM — we have just constructed it), we get
$\varphi_{v}(v) = t(g(Q, v))$.

Finally:

Let’s define $e \coloneqq g(Q, v)$. Then, $\varphi_{e} = \varphi_{t(e)}$. $\square$

## 2º Recurstion Theorem Following is what the second recursion theorem states. Let $f : \N^2 \rightarrow \N$ be a total recursive function.

### Proof

Let’s define:

By applying **s-m-n** theorem it is possible to fix the first two parameters —
$x$ and
$y$ —, thus getting
$\varphi_{s(p, x, y)}(z)$. The function now has only one variable.

So, $\varphi_{s(x, y)} = \varphi_{f(\varphi_{x}(x), y} \text{ if } \varphi_{x}(x) \downarrow$. By construction, $s$ is total (it always terminates) and recursive (can be implemented as a computer program).

So, $\exist t$ total recursive such that:

If we define $g(y) \coloneqq \varphi_{t(y)}(t(y)) = s(t(y), y)$ we get:

(Note that in the proof of the second Recursion Theorem the program $p$ has not been included in the notation throughout the steps to lighten the notation — which is already a bit heavy.)