6. The Kleene Recursion Theorem

Suppose Phil Grates at Macrohard Corp. wants to corner the market with progamming system h[_,_]. He intends to wipe the competing programming system f[_,_] off of the planet by releasing MHVirus into the ambient computing environment. The design team of MHVirus is supposed to find an effective way to screw up the performance of every program in the f[_,_] system. That is, MHVirus is supposed to compute a total recursive function v such that for each n, k,

f[n, k] ¹ f[v(n), k].

The question is, can Phil carry out his diabolical plan successfully?

Here is an analogy from analysis. Suppose we take a unit square. Draw the diagonal from the lower left to the upper right. Now without lifting your pencil from the paper, try to draw a line that crosses the square from left to right without crossing the diagonal line. It isn't possible, because the diagonal is in the way. The line is the graph of a continuous function f: [0, 1] ® [0, 1] and the diagonal is the x = y line. Wherever the graph touches the x = y line, we have y = f(x) = x. Then x is called a fixed point of f.

This point is called a fixed point of the wrinkling process.

Now if Phil Grates' virus is viewed as a "continuous" distortion of the partial recursive functions, we might expect that the diabolical scheme must fail in the (not very useful) sense that at least one program's input-output behavior is unaffected by the virus. That is precisely what happens. In fact, the construction is literally analogous to trying to avoid the diagonal of a square when you try to draw a continuous line across it, as I shall try to bring out in the following proof.

Kleene Recursion Theorem: Let f[n, k] be an acceptable numbering of Part.

"k, " total recursive f, $n, f[n, k] = f[f(n), k].

Proof: The proof of this theorem is facilitated by a convention. Consider the embedded expression

f[f[n, k](x), k'](y).

It is pretty clear that if

f[n, k](x) » z,

then

f[f[n, k](x), k'] = f[z, k'].

But what if f[n, k](x) is undefined? Then our acceptable numbering isn't "given a number to interpret", so f[f[n, k](x), k'](y)
does not denote a function. But there is another way to look at it. Let u be a universal index for acceptable numbering f[_,_]. Now we have that for each y,

f[u, 2](f[n, k](x), <y>),

where means "undefined". Thus, we may also think of the whole expression as denoting the everywhere undefined function

Now let an arbirary, total recursive "virus" f be given.
Think of a two-dimensional table in which the cell T[n, m] is filled by the function f[f[n, 1](m), 1]. The table looks like:

f[f[0, 1](0), 1], f[f[0, 1](1), 1], f[f[0, 1](2), 1], ...
f[f[1, 1](0), 1], f[f[1, 1](1), 1], f[f[1, 1](2), 1], ...
f[f[2, 1](0), 1], f[f[2, 1](1), 1], f[f[2, 1](2), 1], ...
...

(Think of this table as standing in for the unit square of reals in our analogy). Every cell of the table is filled with a partial recursive function because of our convention for dealing with the case in which f[n, 1](m) is undefined. Consider the (bold-face) diagonal of the table. We will now see, remarkably enough, that the diagonal of the table

f[f[0, 1](0), 1], f[f[1, 1](1), 1], f[f[2, 1](2), 1], ...

is also a row of the table

f[f[z, 1](0), 1], f[f[z, 1](1), 1], f[f[z, 1](2), 1], ....

where the function f[z, 1] generating the row is a total recursive function. We do this using the universal and s-m-n properties as follows. Using a universal index u of numbering f[_, _], define partial recursive function

y(n, x) » f[u, 2](f[n, 2](n), <x>) » f[f[n, 1](n), 1](x).

Since f[_, _] is onto Part, choose w such that

f[w, 2](n, x) » y(n, x).

Using the s-m-n property of numbering f[_, _], we obtain a total recursive s such that

f[s(w, n), 1](x) » f[w, 2](n, x).

Now compose in a constant function to obtain a unary total recursive g such that for all n,

g(n) = s(w, n)

Unwinding the defininitions, we obtain:

f[g(n), 1](x) » f[s(w, n), 1](x) » f[w, 2](n, x) » y(n, x)» f[u, 2](f[n, 2](n), <x>) » f[f[n, 1](n), 1](x).

So as promised, the diagonal of the table is also a row of the table generated by a total recursive function:

f[g(n), 1] = f[f[n, 1](n), 1].

Now consider the total recursive virus f. Since g is total recursive, so is C(f, g), so we also have that

f[f(g(0)), 1], f[f(g(1)), 1], f[f(g(2)), 1], ....

is also a row of the table. Now (just as in our attempt to draw a line across the unit square), this row must intersect the diagonal somewhere, say at position n:

f[C(f, g)(n), 1] = f[f[n, 1](n), 1].

Now let's check the effect of the virus f on the index g(n), which exists because g is total.

f[f(g(n)), 1](x) » f[f[n, 1](n), 1](x) » f[g(n), 1](x).

So the behavior of the index g(n) is unaltered by f. Q.E.D.

Exercise 1: Can the theorem be strengthened to a guarantee that the unaffected index is primitive recursive? Total? If your answer is affirmative carry out the proof. If it is negative, prove the negative claim and describe where Kleene's proof fails. You don't understand a theorem unless you do this. Relate the existence or nonexistence of acceptable numberings for classes of total recursive functions to your result.

Good, Kleene Fun

We usually use the recursion theorem in tandem with the universal and s-m-n theorems. The recursion theorem can generate wonderful curiosities, like the self-printing program. At first it seems easy to make a self-printing program: something like

print(progam).

But that won't do because what is printed is program, not the actual program print(progam). Now we start to wonder if it is possible. It looks like there might be an infinite referential regress, in which the program tries forever to refer to itself but always misses the outermost "print" command in its own program. We would like to say

print(me),

but can programs be self-conscious? Some can. Let's construct one. The projection function p_2,2 is partial recursive. So let

f[n, 2] = p_2,2.

Now apply the s-m-n theorem to obtain a total recursive s such that for all x,

f[s(n, x), 1](y) »f[n, 2](x, y) » p_2,2(x, y).

Now compose in a constant function and the appropriate projections to obtain a total recursive g such that

g(x) = s(n, x).

By the Kleene recursion theorem, we obtain an m such that

f[g(m), 1] = f[m, 1].

Thus, for each x:

f[m, 1](x) » f[g(m), 1](x) » f[s(n, m), 1](x) »f[n, 2](m, y) » p_2,2(m, y) = m.

Exercise 2: Show that each partial recursive function has a finite variant that is "self-referential" in the sense that the first argument on which the function is nonzero is an index for the function.

Exercise 3: Show that double recursion over partial recursive functions yields a partial recursive function. Before we only said that it is "intuitively effective". By the Church-Turing thesis it follows that double-recursion is partial recursive. But we can now prove this fact formally, bypassing the Church-Turing thesis. Hint: follow the pattern of the preceding example. Write an expression for the recursion in which the recursive call is just a free variable. Apply s-m-n to this variable position and then apply Kleene's fixed point theorem. This is why it's called the "recursion theorem".

The Kleene recursion theorem has far wider significance than these examples suggest. As we will see, it is a powerful way of turning purely computational problems into empirical problems.