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.

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

Advertisements