## The Recursion Theorem

The standard proof of the recursion theorem is slick but unintuitive. This is my attempt to give a proof that is easier to understand.

Theorem (Kleene)
If ${f: \omega \rightarrow \omega}$ is a recursive function, then there exists an $x \in \omega$ such that the Turing machine indexed by $x$ is equivalent to the Turing machine indexed by $f(x)$ i.e. $\{x\} \simeq \{f(x)\}$.

Proof
Fix a recursive function $f$. Our plan is to build a computable sequence of Turing machines $\{\varphi_{e_i}\}_{i \in \omega}$ so that each machine in this sequence attempts to do two things. First the machine ‘tries’ to determine its own index $e_i$ by running a computation. Secondly if the machine obtains an answer $x$ to this computation, then the machine emulates the machine numbered $f(x)$. Note that if machine $e_i$ correctly determines its own index, then $x=e_i$ and so $\{e_i\} \simeq \{f(e_i)\}$.

How should the machine $e_i$ attempt to guess its own index? Well assuming that the function $g$ defined by $g(i) =e_i$ is recursive, there is some $a$ such that $\{a\} \simeq g$ and so obviously $\{a\}(a) =g(a) = e_a$. This indicates that machine $\varphi_{e_i}$ should guess that its index is $\{i\}(i)$. Hence let $\varphi_{e_i}$ be a Turing machine that first computes $\{i\}(i)$, then, if this computation terminates, emulates the machine indexed by $f(\{i\}(i))$. The function $g$ defined by $g(i) =e_i$ is recursive because $e_i$ can be computed from the quadruples of a universal machine, an index for $f$ in this machine, and the quadruples that write a sequence of $1$‘s of length $i$ onto the tape.

Let $a$ be an index for $g$. Let $e_a = g(a)$. Machine $e_a$ is the machine that computes $\{a\}(a)$ then emulates $f(\{a\}(a))$. But $a$ is an index for $g$ and $g(a)\downarrow=e_a$. Hence $e_a$ emulates $f(e_a)$ and we are done.

Or simply define $g$ to be a recursive function such that $\{g(i)\} \simeq \{f(\{i\}(i))\}$. Let $a$ be an index for $g$ then $\{g(a)\} \simeq \{f(\{a\}(a))\} = \{f(g(a))\}$.

To show that there is a computable fixed point, observe that an index for the function $g$ is computable in an index for the function $f$.