The Recursion Theorem

Can a machine self-reproduce? Intuition might tell us that a factory must be more complex than its output, however the human body seems to contradict this idea

On a simpler level, can an algorithm “self-reproduce”?

We will construct a Turing machine that prints out a copy of its own description, which we will call $SELF$

To start, we can easily make a computable function $q:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$, where if $w$ is any string, $q(w)$ is the description of a Turing machine $P_w$ that prints out $w$ and then halts

We construct $SELF$ in two parts $A$ and $B$
In whole,

1. $A$: Print $⟨B⟩$ on the tape
2. $B_1$: Look at the tape, calculate $q(⟨B⟩)=⟨A⟩$
3. $B_2$: Combine $A$ and $B$ into $⟨AB⟩=⟨SELF⟩$
4. $B_3$: Print $⟨SELF⟩$ and halt

This construction can be easily done in any programming language

Here’s an English example,

Title

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

In this example, the line with quotes acts as $A$ and the line without acts as $B$

We can extend this technique slightly to obtain the theorem

Recursion theorem: Let $T$ be a Turing machine that computes a function $t:{\Sigma }^{\ast }\times {\Sigma }^{\ast }\to {\Sigma }^{\ast }$. There is a Turing machine $R$ that computes a function $r:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$ where for every $w$, $r(w)=t(⟨R⟩,w)$

In other words, we can make any Turing machine have a copy of its own description

This opens up interesting doors for how we can define a machine, for example now we can write,
$SELF=$ “On any input:

1. Obtain, via the recursion theorem, $⟨SELF⟩$
2. Print $⟨SELF⟩$”

Or a fun proof that a machine $H$ that decides $A_{\text{TM}}$ cannot exist because it leads to contradictions,
$B=$ “On input $w$:

1. Obtain, via the recursion theorem, $⟨B⟩$
2. Run $H$ on $⟨B,w⟩$
3. Do the opposite of what $H$ says.”

Definition: $M$ is minimal if there is no Turing machine equivalent to $M$ that has a shorter description, $MI{N}_{\text{TM}}=\{⟨M⟩\mid M\text{ is a minimal TM}\}$

Theorem: $MI{N}_{\text{TM}}$ is not Turing-recognizable

Assume that some $\text{TM}$ $E$ enumerates $MI{N}_{\text{TM}}$ and obtain a contradiction,
$C=$ “On input $w$:

1. Obtain, via the recursion theorem, $⟨C⟩$.
2. Run $E$ until a machine $D$ appears with a longer description than $C$.
3. Simulate $D$ on $w$.”

Definition: A fixed point of a function is a value that isn’t changed by application of the function

Theorem: Let $t:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$ be a computable function, then there is a Turing machine $F$ for which $t(⟨F⟩)$ describes a Turing machine equivalent to $F$

$F=$ “On input $w$:

1. Obtain, via the recursion theorem, $⟨F⟩$
2. Compute $t(⟨F⟩)=⟨G⟩$
3. Simulate $G$ on $w$.”