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:
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.
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: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$:
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$:
$SELF =$
When we turn on the Turing machine $SELF$, the following things happen:
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 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.
The recursion theorem allows us to define the $SELF$ Turing machine very succinctly:
$SELF =$ "On any input:
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$:
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.
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:
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.
Copyright © 2024 Ian Finlayson | Licensed under a Creative Commons BY-NC-SA 4.0 License.