The Recursion Theorem

Overview

The recursion theorem is a mathematical result dealing with self-reproducible systems. It has applications in logic, computability, quines and computer viruses.

It is sometimes called Kleene's recursion theorem after Stephen Kleene who proved it in 1938.

Consider the following paradox:

Living things are machines.
Living things can self-reproduce.
Machines cannot self-reproduce.

Statements 1 and 2 are true. Statement 3 seems true. If machine $A$ produces other machines of type $B$, it would seem $A$ must be more complicated than $B$. Since a machine cannot be more complicated than itself, it seems no machine could produce itself.

However, statement 3 is incorrect. The recursion theorem shows how machines can reproduce themselves.

The SELF Turing Machine

To illustrate the recursion theorem, we will construct a Turing machine, $SELF$ which takes no input, but prints its own description.

To work towards $SELF$, we will define a function $q$. $q$ takes a string $w$ as a parameter and produces the description of a Turing machine which outputs $w$.

The following Turing machine $Q$ computes $q(w)$:

$Q$ = "On input $w$:

Construct the following Turing machine $P_w$:
$P_w$ = "On any input:
1. Erase the input.
2. Write the string $w$ onto the tape.
3. Halt
Output $\langle P_w\rangle$.

If we run $Q$ on input "Hello World!", then $Q$ will output a Turing machine which will print the string "Hello World!".

We will now define the Turing machine $SELF$ in two parts: $A$ and $B$:

$A$ is a Turing machine that prints the description of $B$.
$B$ is a Turing machine that prints the description of $A$.

The two descriptions concatenated $\langle AB \rangle = \langle SELF\rangle$.

The definition of $A$ is simple. $A$ is given using the function $q$ when passed the description of $B$. Creating $A$ assumes we have a description of $B$.

To create $B$, it would be tempting to define it the same way, by applying $q$ to $A$, but that would be a circular definition.

Instead $B$ computes $A$ from the output that $A$ produces. Because $B$ runs after $A$, $B$ can look at the output of $A$ - which is the description of $B$. $B$ can then use this to find the description of $A$ by using the function $q$. $B$ then modifies the tape so that the description of $A$ is inserted before the description of $B$.

The machine $SELF$ is composed of the concatenation of machines $A$ and $B$. After running $A$, then $B$, the tape will contain $\langle AB\rangle$ which is equal to $\langle SELF\rangle$.

To summarize:

$A = q(B)$

$B =$ "On input $\langle M \rangle$:

Compute $q(\langle M\rangle)$.
Place the result of this computation at the beginning of the tape.
Halt.

$SELF =$

Run $A$.
Run $B$.

Meaning of SELF

When we turn on the Turing machine $SELF$, the following things happen:

Turing machine $A$ runs. This erases whatever input $SELF$ got and places a description of $B$ on the tape.
$B$ runs next. $B$ looks at the tape to see its own description. It then calculates $q(B)$ which is a Turing machine that prints $B$, namely $A$.
$B$ puts the description of $A$ before the description of $B$ on the tape.
Now the tape contains a description of $A$ followed by a description of $B$ - which is a description of $SELF$.

The $SELF$ Turing machine is exactly equivalent to a "quine" program which prints its own output. A quine works by containing a quoted version of itself. The quine then prints the quoted text twice - once inside of quotes and one outside.

Part $A$ is the quoted part, and part $B$ is the part that outputs itself.

The $SELF$ Turing machine is the result of importing the sentence:

Print out two copies of the following, the second one in quotes:
"Print out two copies of the following, the second one in quotes:"

Into the language of Turing machines.

The Recursion Theorem

The recursion theorem is a direct extension of the $SELF$ Turing machine. Rather than have $B$ print its description and halt, it can continue on and perform any other computation. The mechanism of obtaining the full description of this Turing machine works the same way.

The recursion theorem states that any Turing machine can obtain its own description.

Mathematically, the recursion theorem says that, given some Turing machine $X$ which takes input $w$, we can algorithmically create another Turing machine $Y$ which takes two inputs: the original string $w$, and a description of $X$, and behaves exactly the same as $X$.

This means that any Turing machine can be modified to compute its own description. At any point in a Turing machine algorithm, we can include the step "Obtain the description of this Turing machine".

This can be used for the purpose of printing the description, as in $SELF$, or in using the description in some computation.

It can also be used in proving different properties of Turing machines.

SELF with the Recursion Theorem

The recursion theorem allows us to define the $SELF$ Turing machine very succinctly:

$SELF =$ "On any input:

Erase all input.
Obtain, via the recursion theorem, own description $\langle SELF\rangle$.
Print $\langle SELF\rangle$.

Another Proof of $A_{TM}$'s Undecidability

The recursion theorem allows us to prove that $A_{TM}$ is undecidable in a more succinct manner.

First, we assume that $A_{TM}$ is decidable in order to obtain a contradiction. Further, assume that Turing machine $H$ decides $A_{TM}$.

Then, construct the following Turing machine $B$:

$B =$ "On input $w$:

Obtain, via the recursion theorem, own description $\langle B\rangle$.
Run $H$ on input $\langle B, w\rangle$.
Do the opposite of what $H$ says."

The machine $B$ asks $H$ whether it, $B$, accepts $w$ or not. It then does the opposite of whatever $H$ tells it to do, creating a contradiction.

Because $B$ is a contradiction built from $H$, $H$ cannot exist and $A_{TM}$ must be undecidable.

Quines

GEB mentions "quines" which are self-producing sentences. One example from the reading is:

"Yields falsehood when preceded by its quotation" yields falsehood when preceded by its quotation.

In programming a quine is a program which, when run, produces its own source code as output - the program version of the $SELF$ Turing machine.

Rules for quines:

The program must be non-empty.
The program cannot read its source from a file.

Below is a Java quine program from wikipedia.


public class Quine
{
  public static void main(String[] args)
  {
    char q = 34;      // Quotation mark character
    String[] l = {    // Array of source code
    "public class Quine",
    "{",
    "  public static void main(String[] args)",
    "  {",
    "    char q = 34;      // Quotation mark character",
    "    String[] l = {    // Array of source code",
    "    ",
    "    };",
    "    for(int i = 0; i < 6; i++)           // Print opening code",
    "        System.out.println(l[i]);",
    "    for(int i = 0; i < l.length; i++)    // Print string array",
    "        System.out.println(l[6] + q + l[i] + q + ',');",
    "    for(int i = 7; i < l.length; i++)    // Print this code",
    "        System.out.println(l[i]);",
    "  }",
    "}",
    };
    for(int i = 0; i < 6; i++)           // Print opening code
        System.out.println(l[i]);
    for(int i = 0; i < l.length; i++)    // Print string array
        System.out.println(l[6] + q + l[i] + q + ',');
    for(int i = 7; i < l.length; i++)    // Print this code
        System.out.println(l[i]);
  }
}

This quine program, and the quine sentence, are direct applications of the recursion theorem.