The Recursion Theorem

The Recursion Theorem#

This section generalizes the existence of self-writing programs to prove one of the cornerstone results of computability theory, Kleene’s Second Recursion Theorem.

Theorem 9

For every word $p$ there is some word $q^*$ so that for all $r$,

\[ [\![ q^* ]\!](r) \simeq [\![p]\!] (q^*,r) \]

The basic idea in this proof is that $q^*$ should be a word of the form $[\![\hat{q}]\!](\hat{q})$. So we first write a program $\hat{q}$ so that for all $r$ and all programs $x$ which mention only the first three registers,

\[ [\![ [\![\hat{q}]\!](x)]\!](r) \simeq [\![p]\!]([\![x]\!](x) ,r) \]

Then we set $x = \hat{q}$ to see that for all $r$

(1)#\[[\![ [\![\hat{q}]\!](\hat{q})]\!](r) \simeq [\![p]\!]([\![\hat{q}]\!](\hat{q}) ,r)\]

When we take $q^* = [\![\hat{q}]\!] (\hat{q})$, we see that

\[ [\![ q^* ]\!](r) \simeq [\![p]\!] (q^*,r) \]

This is the desired equation. Now to get $\hat{q}$, we take

\[ diag + move(1,2) + [\![write]\!](move(1,4)) + move(2,1) + [\![write]\!](move(4,2) + p) \]

This only mentions R1, R2, and R3. (R3 is mentioned in $diag$.) Then for all $x$ which also mentions only those registers,

\[ [\![\hat{q}]\!](x) \simeq move(1,4) +[\![diag]\!](x) + move(4,2) + p \]

In particular,

\[ [\![\hat{q}]\!] (\hat{q}) = move(1,4) +[\![diag]\!] (\hat{q}) + move(4,2) + p \]

Then a routine calculation shows that (1) above holds. (It is here that we us the assumption that $\hat{q}$ mentions only the the first three registers.) This last equation was our goal, and so we are done.

Recall that a quine is a program $q$ such that $[\![ q ]\!](\ ) \simeq q$. Our program $[\![ diag]\!](diag) \simeq self$ is a quine. We used a similar construction i proving the Recursion Theorem, so it is not surprising that the theorem is much more general and implies easily that quines exist.

Example: quines derived from the Recursion Theorem

Take $p$ to be a program computing the first projection on two variables, so $[\![ p ]\!](q,r) \simeq q$ for all $q$, $r$. By the Recursion Theorem, there is some $q^*$ so that for all $r$,

\[ [\![ q^* ]\!](r) \simeq [\![p]\!] (q^*,r) \simeq q^*. \]

In particular, $[\![ q^* ]\!](\ )\simeq q^*$.

Exercise 63

Show that there are infinitely many non-equivalent quines by showing that for all $n$, there is a program $q_n$ such that

\[\begin{split} \begin{array}{lcl} [\![ q_n ]\!](x) & = & \left\{ \begin{array}{ll} q_n & \mbox{if $x = \varepsilon$}\\ 1^n &\mbox{if $x\neq \varepsilon$} \end{array} \right. \end{array} \end{split}\]

Kleene’s proof#

The proof of Theorem 9 above begins with the idea that the program $q^*$ should be of the form $[\![\hat{q}]\!] (\hat{q})$. The original proof, due to Kleene, goes a little differently. It starts with the idea that $q^*$ should be of the form

\[ [\![s^1_1]\!] (p',p') \]

for some program $p'$ which is built from $p$. Indeed, we take $p'$ to be a program with the property that

\[ [\![p']\!] (x, y) \simeq [\![p]\!]([\![s^1_1]\!](x, x), y) \]

And then a routine calculation shows that this works: taking $q^* = [\![s^1_1]\!] (p',p')$ gives a program with the desired equation $[\![ q^*]\!](r) \simeq [\![ p]\!](q^*,r)$.

Another form of the Recusion Theorem#

Here is a second form of the Recursion Theorem, due (?) to Hartley Rogers in his famous book.

Theorem 10

For every computable $f: Words \to Words$ there is a program $p^*$ so that $[\![p^*]\!] = [\![f(p^*)]\!]$.

Here is the proof. Let $y$ be a program which computes $f$. That is, for all $x$,

\[ f(x) = [\![y]\!](x) \]

Let $z$ be a program so that for all $p$ and $r$, $[\![z]\!](p,r) = [\![ [\! [y]\!](p) ]\!] (r)$. For example, $z$ could be

\[ move(2,k) + y + move(k,2) + u_1 \]

where $k$ is large enough so that $y$ does not mention Rk, and $u_1$ is as in our work on the universal program.

By Theorem 9, we have some $p^*$ so that

\[ [\![p^*]\!](r) = [\![ [\! [z]\!](p^*) ]\!] (r) = [\![ [\! [y]\!](p^*) ]\!] (r) = [\![f(p^*)]\!](r). \]

This completes the proof.

Here is a corollary which illustrates the power of this form of the Recursion Theorem.

Corollary 2

There is a word $p^*$ so that for all $r$, $[\![p^*]\!](r) = r + p^*$.

Proof. Take $f$ to be $[\![write]\!]$. Then $f$ is total. By Theorem 10, let $p^*$ be such that $[\![p^*]\!] = [\![ [\![write]\!](p^*) ]\!]$. Then for all $r$,

\[ [\![p^*]\!](r) = [\![ [\![write]\!](p^*) ]\!] (r) = r + p^* \]

Exercise 64

Show that Theorem 9 follows from Theorem 10.

Computability of functions defined by recursion#

One important application of the Recursion Theorem is that functions may be defined by recursion in ways that go beyond primitive recursion. Here is what we have in mind. Consider the following three function definitions:

\[\begin{split} \begin{array}{lcl} gcd(x,y) & = & \left\{ \begin{array}{ll} x & \mbox{if $y=0$} \\ \gcd(y, rem(x,y))) & \mbox{otherwise} \end{array} \right. \\ \\ A(x,y) & = & \left\{ \begin{array}{ll} y+1 &\mbox{if $x=0$} \\ A(x-1,1) & \mbox{if $x\neq 0$ and $y=0$}\\ A(x-1,A(x,y-1)) & \mbox{otherwise} \end{array} \right. \\ \\ collatz(n) & = & \left\{ \begin{array}{ll} 1 &\mbox{if $n \leq 1$} \\ 1 + collatz(n/2) & \mbox{if $n\geq 2$ is even } \\ 1 + collatz(3n) & \mbox{if $n\geq 3$ is odd} \end{array}\right. \end{array} \end{split}\]

In the first of these, $rem(x,y)$ is the remainder when $y$ is divided by $x$.

In all three function definitions, the right-hand side includes calls to the same function which is being defined, but those calls are more complicated than what is allowed by primitive recursion. So from the form in which we have written them, it is not clear from first principles that any of these are computable in the first place.

In the case of $gcd$, we can reformulate the function to see that it is primitive recursive:

\[ gcd(x,y) = \mbox{the largest $z \leq x,y$ such that $z | x$ and $z| y$} \]

Indeed, this is the usual definition of the function $gcd$, whereas the recursive expression comes later. But suppose that we started with the recursion. Better yet, suppose that we modified it to change $rem$ to some other two-place computable function, say $a(x,y)$. Then it would not be so clear that the modified funciton were computable.

Turning to $a(x,y)$ itself, we have argued that it is not primitive recursive in the first place. Now is the time to check that it is computable and also total. Finally, $collatz(n)$ is computable, as we shall see shortly. Put more accurately, there is a computable partial function that satisfies the recursion equation for $collatz$ that we see above. The issue is that we do not know whether the computable partial function that we are going to see is total or not.

The details which show that all three example functions are computable are similar. We illustrate with $A(x,y)$. Let $f$ be a total computable function so that for all programs $p$, $f(p)$ is a program with the property that

\[\begin{split} [\![ f(p)]\!](x,y) & = & \left\{ \begin{array}{ll} y+1 &\mbox{if $x=0$} \\ [\![p]\!](x-1,1) & \mbox{if $x\neq 0$ and $y=0$}\\ [\![ p]\!]\biggl(x-1, [\![p]\!](x,y-1) \biggr) & \mbox{otherwise} \end{array} \right. \end{split}\]

It should be clear how to get a computable $f$ with this property, using the universal function.

Now by Theorem 10, there is some $p^*$ such that $[\![p^*]\!] = [\![f(p^*)]\!]$. This function would satisfy

\[\begin{split} [\![ p^*]\!](x,y) & = & \left\{ \begin{array}{ll} y+1 &\mbox{if $x=0$} \\ [\![p^*]\!](x-1,1) & \mbox{if $x\neq 0$ and $y=0$}\\ [\![ p^*]\!]\biggl(x-1, [\![p^*]\!](x,y-1) \biggr) & \mbox{otherwise} \end{array} \right. \end{split}\]

In other words, it would satisfy the same recursion equations as $gcd$. Now it is a separate mathematical fact that the function $gcd$ is the unique function that satisfies the recursion equations above. Then the uniqueness implies that $gcd = [\![p^*]\!]$. And since we already know that $gcd$ is computable (even primitive recursive), the treatment using the Recursion Theorem does not add much.

(On the other hand, it does add a complexity fact. Indeed, the Euclidean algorithm is known to be the best, in some precise (but technical) sense.)

Now we turn to $A(x,y)$. In this case, what we have seen with the Recursion Theorem implies that there is a computable function that satisfies the recursion equations of $A(x,y)$. It does not imply that there is a unique such function. However, a separate result would indeed show that. Here is a way to state that result. Suppose we have two functions $A$ and $B$, and

\[\begin{split} \begin{array}{c} \begin{array}{lcl} A(x,y) & = & \left\{ \begin{array}{ll} y+1 &\mbox{if $x=0$} \\ A(x-1,1) & \mbox{if $x\neq 0$ and $y=0$}\\ A(x-1,A(x,y-1)) & \mbox{otherwise} \end{array} \right. \end{array} \\ \\ \begin{array}{lcl} B(x,y) & = & \left\{ \begin{array}{ll} y+1 &\mbox{if $x=0$} \\ B(x-1,1) & \mbox{if $x\neq 0$ and $y=0$}\\ B(x-1,B(x,y-1)) & \mbox{otherwise} \end{array} \right. \end{array} \end{array} \end{split}\]

We would prove by induction on $x$ that

\[ \mbox{for all $y$, $A(x,y)=B(x,y)$} \]

For $x = 0$, we have $A(0,y) = y+1 = B(0,y)$.

Assuming our result for $x$, we show our goal statement about $x+1$ by induction on $y$. For $y = 0$,

\[ A(x+1,0 ) = A(x,1) = B(x,1) = B(x+1,0) \]

And assuming $A(x+1,y) = B(x+1, y)$, we have

\[\begin{split} \begin{array}{lcll} A(x+1,y+1) & = & A(x,A(x+1,y)) & \mbox{by def of $A$} \\ & = & B(x,A(x+1,y))& \mbox{by induction hypothesis on $x$} \\ & = & B(x,B(x+1,y)) & \mbox{by induction hypothesis on $y$} \\ & = & B(x+1,y+1)& \mbox{by def of $B$} \\ \end{array} \end{split}\]

Finally, we come to the Collatz function. The Recursion Theorem implies that there is a computable funcction satisfying the recursion equations for $collatz$. It does not tell us that this function is total. Indeed, the totality of this function is equivalent to the Collatz conjecture, and this is an open question. We also do not know whether there is just one partial function that satisfies the recursion equations, but this, too, is equivalent to the Collatz conjecture.

It is also easy to think of examples where there are more than one partial function satisfying a set of recursion equations. One is

\[ Bad(x) \simeq Bad(x+1) \]

Here all of the constant functions are solutions (and vice-versa). The most natural solution would seem to be the empty function, and surely this is what our way of proving the Recursion Theorem would give.