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

\[\begin{equation*} \label{eq:K2}\tag{1} [\![ q^* ]\!](r) \simeq [\![p]\!] (q^*,r) \end{equation*}\]

The basic idea in this proof is that $q^*$ should be a word of the form $\semantics{\hat{q}}(\hat{q})$. We make this leap of faith based on what we saw with the self-writing program in the last section.

We first write a program $\hat{q}$ so that for all $r$ and all programs $x$ which mention only the first three registers,

\[\begin{equation*} \label{qhat} \tag{2} \semantics{\semantics{\hat{q}}(x)}(r) \simeq \semantics{p}(\semantics{x}(x) ,r) \end{equation*}\]

We want to be sure that our program $\hat{q}$ itself only uses the first three registers. Then we set $x = \hat{q}$ to see that for all $r$

\[\begin{equation*} \label{recursion-theorem}\tag{3} \semantics{\semantics{\hat{q}}(\hat{q})}(r) \simeq \semantics{p}(\semantics{\hat{q}}(\hat{q}) ,r) \end{equation*}\]

When we take $q^* = [\![\hat{q}]\!](\hat{q})$ in $\eqref{recursion-theorem}$, we see that $\eqref{eq:K2}$ holds.

Thus, we reduce everything to the matter of writing $\hat{q}$ as in $\eqref{qhat}$. We take

\[ \diagprog + \moveprog_{1,2} + \semantics{\writeprog}(\moveprog_{1,4} ) + \moveprog_{2,1} + [\![\writeprog]\!](\moveprog_{4,2} + p) \]

We’ll see in a minute where the 4 comes from as we check that $\eqref{qhat}$ holds. Note that $\hat{q}$ only mentions R1, R2, and R3. (The program $\diagprog$ mentions these three registers only, and every program of the form $\semantics{\writeprog}(y)$ only mentions R1, no matter what $y$ is.) Then for all $x$,

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

So

\[ \semantics{\semantics{\hat{q}}(x)}(r) \simeq \semantics{ \moveprog_{1,4} +\semantics{\diagprog}(x) + \moveprog_{4,2} + p}(r) \simeq \semantics{p}(\semantics{x}(x),r). \]

This last point is exactly where we use the assumption that $x$ mentions only the first three registers: when we run the program $\semantics{\diagprog}(x)$ there is nothing in the first three registers and $r$ is in R4, so this computation gives $\semantics{x}(x)$, as desired. This completes the proof.

Recall that a self-writing program is a program $q$ such that $\semantics{q}(\ ) \simeq q$. Our program $ \selfprog$ is such a program. Our proof of the Recursion Theorem was not so far from our derivation of $\selfprog$, so it is not surprising that the theorem is more general and implies easily that self-writing programs 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 81

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}\]

Exercise 82

Write two “twin” programs $s$ and $t$ with the properties that $s$ and $t$ are different programs; running $s$ with all registers empty gives $t$ in R1; and running $t$ with all registers empty gives $s$ in R1.

“Different” here means that $s$ and $t$ are not symbol-for-symbol the same.

Exercise 83

Write a program $\tradeprog$ which trades places with its input in R1. That is, for all $x$,

\[ [\![ \tradeprog]\!](x) \simeq [\![x]\!](\tradeprog). \]

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

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

Exercise 84

Show that this works: Let $p'$ be any program with the property in (1), and let $q^* = [\![s^1_1]\!] (p',p')$. Show that this program $q^*$ satisfies the equation $[\![ q^*]\!](r) \simeq [\![ p]\!](q^*,r)$.

Another form of the Recursion Theorem#

Here is a second form of the Recursion Theorem, due to Hartley Rogers.

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$, $\semantics{z}(p,r) = \semantics{\semantics{y}(p)}(r)$. For example, $z$ could be

\[ \moveprog_{2,k} + y + \moveprog_{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 $[\![\writeprog]\!]$. Then $f$ is total. By Theorem 10, let $p^*$ be such that $[\![p^*]\!] = [\![ [\![\writeprog]\!](p^*) ]\!]$. Then for all $r$,

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

Exercise 85

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