Advanced Computability

Kleene’s Recursion Theorem

Motivation

• Self Reproduction: A car factory must be more complex than the cars it produces. Can machines construct replicas of themselves?

Self-Pringting Machines

• Can we design a Turing machine that ignores its input and prints a copy of its own description?

Lemma

There is 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 a TM $SELF$ that prints ites code on the tape.

• TM $SELF$ contains two parts $A$ and $B$
• $A$ runs first and passes the control to $B$ once completed
• $A$ uses the machine $P_{⟨B⟩}$, described by $q(⟨B⟩)$
  • So $A$ depends on machine $B$ and we cannot complete its description without specifying the details of $B$
• Construct $B$
  • We cannot define it to be $q(⟨A⟩)$ as it will be circular
  • However, we can computes $A$ from the output $A$ produces
  • On input $⟨M⟩$, $B$ compute $q(⟨M⟩)$, combine the result with $⟨M⟩$ to make a complete TM, then it print the description of this TM and halt

If we now run $SELF$,

1. First $A$ runs and it prints $⟨B⟩$
2. Then $B$ starts and get $⟨B⟩$
3. $B$ calculates $q(⟨B⟩)=⟨A⟩$ and combines that with $⟨B⟩$ into a TM, which is $⟨SELF⟩$
4. $B$ prints $⟨SELF⟩$ and halt Impressive!

We can actually implement this construction in any Turing complete programming language to obtain a program that outputs a copy of itself.

s='s=%r;print(s%%s)';print(s%s)

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

Kleene’s Recursion Theorem

Kleene's Recursion Theorem

Let $T$ be a TM that computes a function $t:{\Sigma }^{\ast }\times {\Sigma }^{\ast }\to {\Sigma }^{\ast }$. There exists a TM $R$ computing function $r:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$ such that for every $w$, $r(w)=t(⟨R⟩,w)$

We construct a TM $R$ in three parts $A,B,T$.

1. $A=P_{⟨BT⟩}$, here we redesign it so that $P_{BT}$ writes its output after the input $w$ to preserve it.
2. $B$ is the machine that finds the $⟨BT⟩$ part on the tape and runs $q$ to obtain $⟨A⟩=q(⟨BT⟩)$. Then $B$ combines $A,B$ and $T$ into a single machine and obtains its description $⟨ABT⟩=⟨R⟩$. $B$ then transforms the content of the tape to $⟨R⟩,w$ and passes control to $T$.

Applications

• The theorem states that Turing machines can obtain their own description and then go on to compute with it
• Except for making a machine that prints a copy of itself, it can be used to prove undecidability

Example

$$AC{C}_{TM}=\{⟨M,w⟩|M\text{ accepts }w\}\text{ is undecidable.}$$

Assume there is a TM $H$ decides $AC{C}_{TM}$.

Consider machine $B$: On input $w$, $B$ obtains its own description $⟨B⟩$ and runs $H$ on input $⟨B,w⟩$, then it does the oppotite of what $H$ says!

$H$ does not perform as required on $⟨B,w⟩$.

Minimal Machine

We say a TM $M$ is minimal if no TM equivalent to $M$ has shorter description. And we claim that the set of minimal TM $MI{N}_{TM}$ is not Turing recognizable.

If it is, we can find a enumerator $E$ that enumerates $MI{N}_{TM}$.

We can construct a TM $C$: On input $w$, it obtain its description $⟨C⟩$, then run $E$ and find the first TM $D$ such that $⟨D⟩$ is longer than $⟨C⟩$. Now it simulates $D$. So $C$ is equivalent to $D$ but $⟨C⟩$ is shorter than $⟨D⟩$. Contradiction.

Roger's Fixed-Point Theorem

Let $t:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$ be a computable function. Then there is a TM $F$ for which $t(⟨F⟩)$ describes a machine equivalent to $F$.

Consider machine $F$: On input $w$, it obtains $⟨F⟩$, compute $t(⟨F⟩)$ to obtain the description of a TM $G$, then it simulate $G$ on $w$.

Gödel’s Incompleteness Theorems

A proof system is an algorithm $V$ that satisfies:

1. Effectiveness: For every statement $x$ and proof string $w$, $V(x,w)$ halts with output either 0 or 1. (It can judge whether a proof is correct)
2. Soundness: If $x$ is not true, then for every $w$, $V(x,w)=0$ Completeness: True statements can be proved.

Gödel's Incompleteness Theorems

Any mathematical proof system which is sufficiently expressive and has computable axioms, cannot be both complete and consistent.

Consider the Halting problem $HAL{T}_{ϵ}=\{⟨M⟩|M\text{ halts on the empty input}\}$:

If $M$ halts on input $w$, there is a mathematical proof for it.

Define TM $D$: On any input, it

1. Obtain own description $⟨D⟩$
2. For all $k=1,2,\dots$ and all strings $P$ of length $k$:
   1. Check if $P$ is a valid ZFC proof for the statement ’ $D$ halts’. If yes, then $D$ loop forever.
   2. Check if $P$ is a valid ZFC proof for the statement ’ $D$ loops’. If yes, halt.