Here we give an illustrative proof of Kleene’s recursion theorem, a fundamental theorem in computability/recursion theory. The proof is so simple it can be stated in few lines. On the other hand, the proof is a beauty in itself (after you get hold of it). Without further ado, we will first state the preliminary definitions/lemmas/theorems and then give the formal statement.

Preliminaries

The words recursive and computable mean the same thing, and can be used interchangeably.

A partial function is defined on only some inputs. A total function is defined on all inputs. Here, inputs are natural numbers. If a function $\phi$ is not defined on some input $x$, we say that $\phi(x)$ diverges, denoted by $\phi(x)\uparrow$. Otherwise, if we can compute $y=\phi(x)$, we say that $\phi(x)$ converges, denoted by $\phi(x)\downarrow$.

Every partial computable function is computable by a Turing Machine (TM). This is the famous Church-Turing Thesis. The inputs on which this function is undefined, the Turing Machine will produce no answer. Hence there exists a TM program for every partial function. The entire description of this program can be uniquely converted to a natural number. Thus the partial computable function which is computed by the TM program with description $x$ is denoted by $\phi_x$, where $x$ is a natural number.

Consider any partial recursive function $\phi_x(m,n)$. The S-m-n theorem (in its simplest form) tells us that there exists a total computable function $f(x,m)$ such that $\phi_x(m,n) = \phi_{f(x,m)}(n)$ for all $m$. In other words, it is possible to find (by a TM) a partial recursive function $\phi_{f(m)}(n)$ which has the same input-output mapping as $\phi_x(m,n)$ for all inputs $n$. You can think about it as hard-wiring one or more input-arguments of any function into its index.

Now we are ready to state the recursion theorem.

The Statement

Kleene’s Recursion Theorem tells us that for every total computable function $f$ which takes a natural number as input and gives another natural number as output, there exists a particular input $n$ such that the two partial computable functions $\phi_n$ and $\phi_{f(n)}$ have the same input-output characteristics.

In other words,

1. Pick any computable function $f$ that is total.
2. Then, there exists some natural number $n$, such that
3. If we grab the two partial functions $\phi_n$ and $\phi_{f(n)}$, we will see that
4. Wow! They have the same input-output mapping for all inputs, that is,
1. If $\phi_n(x)$ diverges for some $x$, so does $\phi_{f(n)}(x)$.
2. If $\phi_n(x)$ converges for some $x$, so does $\phi_{f(n)}(x)$ and moreover, $\phi_n(x)=\phi_{f(n)}(x)$.

This is the same as saying that every total computable function $f$ has an input element $n$ such that the two partial functions indexed by $n$ and $f(n)$ will behave identically on all inputs. In this sense, $n$ is called the fixed-point for the total computable function $f$.

The Proof

The proof is elegant and short. However, it contains (like most recursion theory proofs) self-references and therefore sometimes hard to visualize for a beginner. Below we will outline the proof presented to our class lecture by Professor Johanna Franklin.

Figure 1: Components for the proof of Kleene’s recursion theorem.

Step 1. Consider a total, one-to-one function $d$ with one input. We will define this function later. This function maps the given natural number to another natural number.

Step 2. Consider any total computable function $f$, which also maps a given natural number to another natural number.

Step 3. Now consider the composition of $f\circ d$, that is, the result of successively applying $d$ and $f$ on some input. Clearly, since both $f$ and $d$ are total, the composition will also be total. Let $\phi_v$ be the total function that computes this composition. Therefore, for all $x, \phi_v(x)=f(d(x))$. Note that $v$ is a fixed number which must exist although we do not know its exact value. Also note that since $\phi_v$ is total, it follows that $\phi_v(v)\downarrow$.

Step 4. Let $n=d(v)$. Since $d$ is a total function, such an $n$ must exist. Now we have $\phi_v(v)=f(d(v))=f(n)$.

Step 5. Now we will define a partial function $\psi(u,z)$ on two inputs, as follows. First, we will evaluate $\phi_u(u)$ (remember that $u$ is an input to our function $\psi$). If  $\phi_u(u)$ converges to some value, say, $y=\phi_u(u)$, then $\psi(u,z)$ gives the same output as $\phi_y(z)$. Note that since $\phi_y$ is partial, this output may or may not converge. Otherwise, if $\phi_u(u)\uparrow$, then our function $\psi$ diverges. This description is given as follows:
$\psi(u,z)=\left\{\begin{array}{ll}\phi_{\phi_u(u)}(z) & \text{if }\phi_u(u)\downarrow\\\uparrow & \text{otherwise}\end{array}\right.$

Step 6. Now it is time to define the total one-to-one function $d$ mentioned at Step 1. We will do it as follows. We will take the partial function $\psi(u,z)$ defined in previous step, then use the S-m-n theorem to show the existence of another partial function $\phi_{d(u)}(z)$ which has identical input-output behavior as $\psi(u,z)$.

Therefore, $d$ is a function which maps a natural number to another natural number. Since the parameter $u$ of the function $\psi(u,z)$ can be any natural number, $d$ is defined for all inputs, and hence total. Moreover, as S-m-n theorem tells us, $d$ is computable as well.

Step 7. Now we have all the pieces of the puzzle. Here we are interested at only one particular number, namely $v$ from Step 3. At Step 3 we showed that $\phi_v$ is total, and hence $\phi_v(v)\downarrow$. Therefore, for any input parameter $z$, we have the following.

$\begin{array}{rcl}\phi_n(z)&=&\phi_{d(v)}(z)\ \ \ \ \text{(Step 4)}\\&=&\psi(v,z)\ \ \ \ \text{(Step 6)}\\&=&\phi_{\phi_v(v)}(z)\ \ \ \ \text{since }\phi_v(v)\downarrow\text{ (Step 5)}\\&=&\phi_{f(n)}(z)\ \ \ \ \text{(Step 4)}\\\end{array}$

$\square$