# Kleene's Recursion Theorems

Published May 19, 2022  -  By Marco Garosi

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.

$\implies \exist e : \varphi_{e} = \varphi_{t(e)}$

First Recursion Theorem

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

### Proof

Let’s define:

$\varphi_{Q}(u, x) = \begin{cases} \varphi_{\varphi_{u}(u)}(x) &\text{if } \varphi_{u}(u) \downarrow \\ \uparrow \text{otherwise} \end{cases}$

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:

$\varphi_{g(Q, v)} = \varphi_{\varphi_{v}(v)} = \varphi_{t(g(Q, v))}$

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.

$\implies \forall y \text{ } \exist g \text{ total recursive} : \varphi_{f(g(y), y)} = \varphi_{g(y)}$

Second Recursion Theorem

### Proof

Let’s define:

$\varphi_{p}(x, y, z) = \begin{cases} \varphi_{f(\varphi_{x}(x), y)}(z) &\text{if } \varphi_{x}(x) \downarrow \\ \uparrow \text{otherwise} \end{cases}$

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

$\implies \exist Q \text{ TM} : \varphi_{s(x, y)} = \varphi_{Q}(x, y)$

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

$\varphi_{s(x, y)} = \varphi_{Q}(x, y) = \varphi_{t(Q, y)}(x)$

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

$\varphi_{g(y)} = \varphi_{t(y)}(t(y)) = \varphi_{s(t(y), y)} = \varphi_{f(\varphi_{t(y)}(t(y), y))} = \varphi_{f(g(y), y)}$

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

Share on: