The previous lesson discussed self-replicating programs. This lesson develops a similar theme, some results from the theory of computability called Recursion Theorems.

As we shall see, the Recursion Theorems are generalizations of the results on self-replicating programs that we saw in Lesson Four and its exercises. So one way to look at things is that the work in the previous lesson is a kind of preparation for the work in the current lesson. But the Recursion Theorems have many uses besides self-replicating programs. In fact, once one delves deeper into the subject, it appears that the the topic of self-replicating programs is but one item in a long list of corollaries of the Recursion Theorems.

Perhaps the main result here is the Recursion Theorem, also called Kleene's Recursion Theorem or even Kleene's Second Recursion Theorem. It was proved by Stephen Kleene, one of the pioneers in recursion theory and other areas of mathematical logic, in 1936.

Here is our main form of the Recursion Theorem:

Let p be any word. Consider φ_p as a function of two words φ_p(q,r).

Then there is a program q* such that for all words r,

Here is our proof of this result.

First, let q1 be the following program:

This is q1. As it turns out, the q* that we are interested in will be φ_q1(q1). It would be a good idea to try to check for yourself that this last program has the required properties, before you read further.

The first thing to note is that the registers used by q1, are R1, R2, and R3.

Let's take a word x and see what φ_q1(x) is.

This is true for all x, in particular with x = q1 itself. So we have

And now we let q* = φ_q1(q1), as promised. Let's see what happens when we run q* with a program r in R1.

If you are reading this carefully, the line to understand is the one "after φ_diag(q1)." Please be sure you get this.

This table completes our proof: it shows that running q* with r in R1 gives the same thing as runing p with q* in R1 and r in R2.

Using the Recursion Theorem

We'd like to see some applications of the Recursion Theorem. Each program p gives us a program q* as in the theorem. What we want to do here is to see how this works in concrete cases. For this, it will be good to actually have most of the code readily at hand.

Recall that we defined q1 as follow

Note that φ_write(move_4,2 + p) = φ_write(move_4,2) + φ_write(p). Each application of the Recursion Theorem uses a different program p. So it makes sense to split that off of the end of this expression. We therefore first consider

Here this is again, written out in full:

Now given p, we need only compute φ_write(p), put this on the right end, and run the result on itself.

For example, suppose p is move_2,1. Then φ_p(q,r) = q + r for all q and r. It follows that for the q* that we construct from the Recursion Theorem,

So running the program q* with a word r in R1 (and all other registers empty) gives q* + r.

To check this, p is

So φ_write(p) is

So q1 here is

And we can check that running this on input words r give out q* + r. Of course, this check is not as convincing as the formal proof.

Smullyan's Recursion Theorem is also called a double recursion theorem. It originates with Smullyan's work in recursion theory connected to the Godel Incompleteness Theorems. Here is our statement of this result.

Let p and q be words. Consider the functions of two arguments φ_p(a,b) and φ_q(a,b). Then there are programs a* and b* so that

(And as always with such results, a* and b* may be derived in a computable way from p and q.)

We turn to our proof. We shall use diag and a few other programs to define a* and b*, and then we'll check that they satisfy the equations above. In parallel with our work on the Recursion Theorem, we'll define programs a1 and b1, and then after that we'll set

Now a1 begins with the instruction to add # to R6

and b1 with the instruction to add # to R7

Please note that these two differ only by a 1. After the beginnings noted just above, a1 and b1 are absolutely identical. We therefore will see to it that b1 = 1 + a1. That is, b1 is 1 followed by a1. We continue to describe the two programs. They proceed with

So executing this initial part of a1 on empty registers puts 1 in R4 and 1## in R5. On the other hand, executing b1 would do the same and also pop the first symbol from R1. It will be helpful to the reader to think about are what happens in the first five registers when the full a1 is run on itself, and similarly with b1. But please remember that we have just started to define these programs. Here is the situation at this point:

We have listed the contents of R1 - R7 for the computations of a1 and b1 on themselves.

The programs a1 and b1 continue with the following doubled version of diag:

Again, we display the first seven registers after this much of a1 and b1:

But note that 1## + φ_write(a1) = φ_write(b1). The programs a* and b* continue as follows:

And so the situation is now described by

Finally, we may look to R6 (or R7) to decide whether to continue with p or q.

And this is it! Putting all of the code items together give the programs a1 and b1, running a1 on itself gives the a* that we are ultimately interested in, and likewise for b1 and b*.

Using the Double Recursion Theorem

Here is a summary of what we have done so far. Starting with words p and q, we constructed a* and b* as follows: a* is

Exercise 1 Which exercises from Lesson 4 on self-replication can be solved using the Recursion Theorem?

Exercise 2 Can one use the Recursion Theorem to construct a program p with the property that p halts if and only if p does not halt?

Exercise 3 Find programs p and q so that φp(p) = 1, φp(q) = #, φq(p) = #, and φq(q) = p. (For x besides p and q, your programs may assign any values to φp(p) and φp(x).)

Exercise 4 The form of the Double Recursion Theorem that we illustrated can be generalized a bit. Your task is to prove the following result and illustrate it with some programs: Let p and q be words. Consider the functions of three arguments φp(a,b,x) and φq(a,b,x). Then there are programs a* and b* so that for all x, φa*(x) = φp(a*,b*,x), and φb*(x) = φq(a*,b*,x).