Kleene's Recursion Theorems

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:

This proves the statement aforementioned. $\square$

(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.)