Carpe diem (Felix's blog)

I am a happy developer

The Recursion Theorem

I’m studying theorem of computation myself. Theorem of computation is an interesting field. It addresses questions as: What is a theorem? What is a proof? What is truth? Can an algorithm decide which statements are true? Can a computer calculates everything in the universe? These questions are linked by the question:

What are the fundamental capabilities and limitations of computers?

This question goes back to the 1930s when mathematical logicians first began to explore the meaning of computation. Thus, three major theorem of computation has born: automata, computability, and complexity. There are a lot of algebras and proofs in this field. Of all the theorems, I love the recursion theorem the most.


First we introduce a Turing Machine that ignores its input and prints out a copy of its own description. We call this machine $SELF$.

There is a computable function $q: \Sigma^\ast\longrightarrow\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.
The following TM $Q$ computes $q(w)$

Now we construct $SELF$ in two parts $A$ and $B$. We want $SELF$ to print out $\langle SELF\rangle = \langle AB\rangle$.