
Recursion Theorems
Welcome
The previous lesson discussed selfreplicating 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 selfreplicating 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 selfreplicating programs. In fact,
once one delves deeper into the subject, it appears that
the the topic of selfreplicating 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 +
move_{1,2} +
φ_{write}(move_{1,4}) +
move_{2,1} +
φ_{write}(move_{4,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 move_{1,2} 

φ_{diag}(x) 

after φ_{write}(move_{1,4})
 move_{1,4} 
φ_{diag}(x) 

after move_{2,1} 
move_{1,4} + φ_{diag}(x)



after φ_{write}(move_{4,2}+p)
 move_{1,4} +
φ_{diag}(x)
+ move_{4,2}+p 


This is true for all x, in particular with
x = q1 itself. So we have
φ_{q1}(q1) =
move_{1,4} +
φ_{diag}(q1) +
move_{4,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 move_{1,4} 



r 
after φ_{diag}(q1)
 φ_{q1}(q1) = q*



r 
after move_{4,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 +
move_{1,2} +
φ_{write}(move_{1,4}) +
move_{2,1} +
φ_{write}(move_{4,2} + p)

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
diag +
move_{1,2} +
φ_{write}(move_{1,4}) +
move_{2,1} +
φ_{write}(move_{4,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 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,
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
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
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:
move_{3,1} 
move_{2,1} 
move_{4,2} 
move_{5,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 selfreplication
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).

