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:

  • TM\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 tt be a total, recursive function.

    e:φe=φt(e) \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, ee.


Let’s define:

φQ(u,x)={φφu(u)(x)if φu(u)otherwise \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 — uu —, thus building a new function which only takes one variable ( xx). The function thus obtained is φg(Q,u)(x)\varphi_{g(Q, u)}(x).

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

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


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

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

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

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

Second Recursion Theorem


Let’s define:

φp(x,y,z)={φf(φx(x),y)(z)if φx(x)otherwise \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 — xx and yy —, thus getting φs(p,x,y)(z)\varphi_{s(p, x, y)}(z). The function now has only one variable.

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

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

So, t\exist t total recursive such that:

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

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

φg(y)=φt(y)(t(y))=φs(t(y),y)=φf(φt(y)(t(y),y))=φf(g(y),y) \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 pp has not been included in the notation throughout the steps to lighten the notation — which is already a bit heavy.)

Share on: