Recursion Theorems
IU Relief
Skip Navigation
1#: A Text Register Introduction to Computability Theory

red horizontal line
red horizontal line
red horizontal line
Recursion Theorems

LESSON Five


Kleene's Recursion Theorem


Smullyan's Recursion Theorem


Exercises


Welcome

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.




Kleene's Recursion Theorem

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,

φp(q*,r) = φq*(r)

Here is our proof of this result.

First, let q1 be the following program:

diag + move1,2 + φwrite(move1,4) + move2,1 + φwrite(move4,2 + p)

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.

R1 R2 R3
at the start x
after diag φdiag(x)
after move1,2 φdiag(x)
after φwrite(move1,4) move1,4 φdiag(x)
after move2,1 move1,4 + φdiag(x)
after φwrite(move4,2+p) move1,4 + φdiag(x) + move4,2+p

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

φq1(q1) = move1,4 + φdiag(q1) + move4,2 + p

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

R1 R2 R3 R4
at the start r
after move1,4 r
after φdiag(q1) φq1(q1) = q* r
after move4,2 q* r
after p φp(q*,r)

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

diag + move1,2 + φwrite(move1,4) + move2,1 + φwrite(move4,2 + p)

Note that φwrite(move4,2 + p) = φwrite(move4,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

diag + move1,2 + φwrite(move1,4) + move2,1 + φwrite(move4,2)

Here this is again, written out in full:

1##### 11111111111### 111111### 11## 111# 111## 111## 1111111#### 11# 111# 111## 11111111111#### 111##### 111111### 111### 1## 1111#### 1# 111111#### 11##### 111111### 111### 1## 1111#### 1# 111111#### 1##### 111111### 111### 11## 1111#### 11# 111111#### 1# 1## 1## 1## 1## 1## 1# 1# 1# 1# 1# 1# 1## 1## 1## 1# 1# 1# 1## 1## 1## 1# 1# 1# 1# 1## 1## 1# 1# 1# 1# 1## 1## 1## 1## 1# 1# 1# 1# 1## 1# 1# 1# 1# 1# 1# 1## 1## 1## 1## 11##### 111111### 111### 1## 1111#### 1# 111111#### 1# 1# 1# 1# 1## 1## 1## 1## 1## 1# 1# 1# 1# 1# 1# 1## 1## 1## 1# 1# 1# 1## 1## 1## 1# 1# 1## 1## 1# 1# 1# 1# 1## 1## 1## 1## 1# 1# 1## 1# 1# 1# 1# 1# 1# 1## 1## 1## 1##

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 move2,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,

q* + r = φq*(r)

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

To check this, p is

11#####111111###111###1##1111####1#111111####

So φwrite(p) is

1# 1# 1## 1## 1## 1## 1## 1# 1# 1# 1# 1# 1# 1## 1## 1## 1# 1# 1# 1## 1## 1## 1# 1## 1## 1# 1# 1# 1# 1## 1## 1## 1## 1# 1## 1# 1# 1# 1# 1# 1# 1## 1## 1## 1##

So q1 here is

1##### 11111111111### 111111### 11## 111# 111## 111## 1111111#### 11# 111# 111## 11111111111#### 111##### 111111### 111### 1## 1111#### 1# 111111#### 11##### 111111### 111### 1## 1111#### 1# 111111#### 1##### 111111### 111### 11## 1111#### 11# 111111#### 1# 1## 1## 1## 1## 1## 1# 1# 1# 1# 1# 1# 1## 1## 1## 1# 1# 1# 1## 1## 1## 1# 1# 1# 1# 1## 1## 1# 1# 1# 1# 1## 1## 1## 1## 1# 1# 1# 1# 1## 1# 1# 1# 1# 1# 1# 1## 1## 1## 1## 11##### 111111### 111### 1## 1111#### 1# 111111#### 1# 1# 1# 1# 1## 1## 1## 1## 1## 1# 1# 1# 1# 1# 1# 1## 1## 1## 1# 1# 1# 1## 1## 1## 1# 1# 1## 1## 1# 1# 1# 1# 1## 1## 1## 1## 1# 1# 1## 1# 1# 1# 1# 1# 1# 1## 1## 1## 1## 1# 1# 1## 1## 1## 1## 1## 1# 1# 1# 1# 1# 1# 1## 1## 1## 1# 1# 1# 1## 1## 1## 1# 1## 1## 1# 1# 1# 1# 1## 1## 1## 1## 1# 1## 1# 1# 1# 1# 1# 1# 1## 1## 1## 1##

Then q* is the following program:

1##### 111111### 111### 1111## 1111#### 1111# 111111#### 1# 1## 1## 1## 1## 1## 1# 1# 1# 1# 1# 1# 1# 1# 1# 1# 1# 1## 1## 1## 1# 1# 1# 1# 1# 1# 1## 1## 1## 1# 1# 1## 1## 1# 1# 1# 1## 1# 1# 1# 1## 1## 1# 1# 1# 1## 1## 1# 1# 1# 1# 1# 1# 1# 1## 1## 1## 1## 1# 1# 1## 1# 1# 1# 1## 1# 1# 1# 1## 1## 1# 1# 1# 1# 1# 1# 1# 1# 1# 1# 1# 1## 1## 1## 1## 1# 1# 1# 1## 1## 1## 1## 1## 1# 1# 1# 1# 1# 1# 1## 1## 1## 1# 1# 1# 1## 1## 1## 1# 1## 1## 1# 1# 1# 1# 1## 1## 1## 1## 1# 1## 1# 1# 1# 1# 1# 1# 1## 1## 1## 1## 1# 1# 1## 1## 1## 1## 1## 1# 1# 1# 1# 1# 1# 1## 1## 1## 1# 1# 1# 1## 1## 1## 1# 1## 1## 1# 1# 1# 1# 1## 1## 1## 1## 1# 1## 1# 1# 1# 1# 1# 1# 1## 1## 1## 1## 1# 1## 1## 1## 1## 1## 1# 1# 1# 1# 1# 1# 1## 1## 1## 1# 1# 1# 1## 1## 1## 1# 1# 1## 1## 1# 1# 1# 1# 1## 1## 1## 1## 1# 1# 1## 1# 1# 1# 1# 1# 1# 1## 1## 1## 1## 1# 1## 1# 1## 1## 1# 1## 1## 1# 1## 1## 1# 1## 1## 1# 1## 1## 1# 1## 1# 1## 1# 1## 1# 1## 1# 1## 1# 1## 1# 1## 1## 1# 1## 1## 1# 1## 1## 1# 1## 1# 1## 1# 1## 1# 1## 1## 1# 1## 1## 1# 1## 1## 1# 1## 1# 1## 1# 1## 1# 1## 1# 1## 1## 1# 1## 1## 1# 1## 1# 1## 1# 1## 1# 1## 1# 1## 1## 1# 1## 1## 1# 1## 1## 1# 1## 1## 1# 1## 1# 1## 1# 1## 1# 1## 1# 1## 1## 1# 1## 1# 1## 1# 1## 1# 1## 1# 1## 1# 1## 1# 1## 1## 1# 1## 1## 1# 1## 1## 1# 1## 1## 1# 1# 1## 1## 1## 1## 1## 1# 1# 1# 1# 1# 1# 1## 1## 1## 1# 1# 1# 1## 1## 1## 1# 1## 1## 1# 1# 1# 1# 1## 1## 1## 1## 1# 1## 1# 1# 1# 1# 1# 1# 1## 1## 1## 1## 1# 1## 1# 1## 1# 1## 1# 1## 1# 1## 1## 1# 1## 1## 1# 1## 1## 1# 1## 1## 1# 1## 1## 1# 1## 1# 1## 1# 1## 1# 1## 1# 1## 1# 1## 1# 1## 1## 1# 1## 1## 1# 1## 1## 1# 1## 1# 1## 1# 1## 1# 1## 1## 1# 1## 1## 1# 1## 1## 1# 1## 1# 1## 1# 1## 1## 1# 1## 1## 1# 1## 1# 1## 1# 1## 1# 1## 1# 1## 1## 1# 1## 1## 1# 1## 1## 1# 1## 1## 1# 1## 1# 1## 1# 1## 1## 1# 1## 1# 1## 1# 1## 1# 1## 1# 1## 1# 1## 1# 1## 1## 1# 1## 1## 1# 1## 1## 1# 1## 1## 1# 1## 1# 1## 1# 1## 1## 1# 1## 1## 1# 1## 1## 1# 1## 1## 1# 1## 1## 1# 1## 1# 1## 1# 1## 1# 1## 1# 1## 1# 1## 1# 1## 1## 1# 1## 1## 1# 1## 1## 1# 1## 1# 1## 1# 1## 1# 1## 1## 1# 1## 1## 1# 1## 1## 1# 1## 1# 1## 1## 1# 1## 1## 1# 1## 1# 1## 1# 1## 1# 1## 1# 1## 1## 1# 1## 1## 1# 1## 1## 1# 1## 1## 1# 1## 1# 1## 1## 1# 1## 1# 1## 1# 1## 1# 1## 1# 1## 1# 1## 1# 1## 1## 1# 1## 1## 1# 1## 1## 1# 1## 1## 1##### 11111111111### 111111### 11## 111# 111## 111## 1111111#### 11# 111# 111## 11111111111#### 111##### 111111### 111### 1## 1111#### 1# 111111#### 11##### 111111### 111### 1## 1111#### 1# 111111#### 1##### 111111### 111### 11## 1111#### 11# 111111#### 1# 1## 1## 1## 1## 1## 1# 1# 1# 1# 1# 1# 1## 1## 1## 1# 1# 1# 1## 1## 1## 1# 1# 1# 1# 1## 1## 1# 1# 1# 1# 1## 1## 1## 1## 1# 1# 1# 1# 1## 1# 1# 1# 1# 1# 1# 1## 1## 1## 1## 11##### 111111### 111### 1## 1111#### 1# 111111#### 1# 1# 1# 1# 1## 1## 1## 1## 1## 1# 1# 1# 1# 1# 1# 1## 1## 1## 1# 1# 1# 1## 1## 1## 1# 1# 1## 1## 1# 1# 1# 1# 1## 1## 1## 1## 1# 1# 1## 1# 1# 1# 1# 1# 1# 1## 1## 1## 1## 1# 1# 1## 1## 1## 1## 1## 1# 1# 1# 1# 1# 1# 1## 1## 1## 1# 1# 1# 1## 1## 1## 1# 1## 1## 1# 1# 1# 1# 1## 1## 1## 1## 1# 1## 1# 1# 1# 1# 1# 1# 1## 1## 1## 1## 1111##### 111111### 111### 11## 1111#### 11# 111111#### 11##### 111111### 111### 1## 1111#### 1# 111111####

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 Double Recursion Theorem

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

φa*( ) = φp(a*,b*), and φb*( ) = φq(a*,b*).

(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

a* = φdiag(a1) and also b* = φdiag(b1)
So that
φa*( ) = φa1(a1) and also φb*( ) = φb1(b1)

Now a1 begins with the instruction to add # to R6

111111#####

and b1 with the instruction to add # to R7

1111111#####

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

111111##### Cases on R6
111### Go forward 3
1### forget about 1
11111### Go forward 5
1#####1###1### pop the first symbol from R1
1111# Add 1 to R4
11111#11111##11111## Add 1## to R5

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:

R1 R2 R3 R4 R5 R6 R7
a1 a1 1 1## 1
b1 a1 1 1## 1

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:

1##### Cases on R1
111111111111111111### Go forward 18 (to below the tan section)
1111111111### Go forward 10 (to the tan section)
11## Add # to R2 (the # branch is in blue)
111#111##111## Add 1## to R3
1111## Add # to R4
11111#11111##11111## Add 1## to R5
11111111111#### Go backward 11
1## Add 1 to R2
111#111## Add 1# to R3
1111# Add 1 to R4
11111#11111## Add 1# to R5
111111111111111111#### Go backward 18

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

R1 R2 R3 R4 R5 R6 R7
runging a1 on itself a1 φwrite(a1) 1+ a1 1## + φwrite(a1) 1
runing b1 on itself a1 φwrite(a1) 1+ a1 1## + φwrite(a1) 1

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

move3,1 move2,1 move4,2 move5,2

And so the situation is now described by

R1 R2 R3 R4 R5 R6 R7
runging a1 on itself φdiag(a1) φdiag(b1) 1
runing b1 on itself φdiag(a1) φdiag(b1) 1

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

111111##### Cases on R6
1|q| + 8 ### Go forward (to the tan section)
11### Go forward 2(to the blue section)
1### R6 does not have #
q (one of the programs we started with)
1111111#####1#1# pop the 1 from R7
1|p|+1 ### Go to the end
p (the other program we started with)

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




Exercises

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).



Last updated: 12 November 2007
Comments: lsm at cs dot indiana.edu
Copyright 2014, The Trustees of Indiana University
Copyright Complaints