Kleene's second recursion theorem

You will need to know the basics of partial recursive functions for this one, but believe me, it's worth the effort. If $e$ is a number, we use the standard notation $\{e\}$ for the partial function whose code is $e$. The theorem says the following:

Theorem A. For any total computable function $F$ there exist an $e$ such that $\{ e \} \simeq \{ F e \}$.

Just think about it. $F$ can be any total computable function! Take $F(x) = x+1$, for instance. That's certainly computable. The theorem says that there exists two successive natural numbers $e$ and $e + 1$ that code the same function, i.e. $\{e\} \simeq \{ e+1 \}$ . Isn't that just amazing?

The crucial idea of the proof is self-application, i.e. the fact that we can apply a function to its own code as $\{e\}(e)$. Moreover, that this self-application is itself computable, i.e. there is a computable function $h$ such that $\{ h(e) \} \simeq \{ \{e\}(e) \}$. 

The proof of the theorem goes as follows:

(1) Assume a total computable function $F$ is given.

(2) For any $x$ let $h (x)$ be a code such that $\{ h(x) \} \simeq \{ \{x\}(x) \}$. Such total and computable function $h$ exists.

(3) Let $k$ be such that $\{k\}(x) \simeq F(h(x))$. Such $k$ exists because both $F$ and $h$ are computable.
(4) We claim that $e = h(k)$ does the job!
(5) By (2) and (4) we have $\{e\}(x) \simeq \{h(k)\}(x) \simeq \{\{k\}(k)\}(x)$.
(6) But by (3) we also have $\{\{k\}(k)\}(x) \simeq \{F(h(k)\}(x) \simeq \{F(e)\}(x)$, so we are done.

An absolute gem, don't you think!?

If you also know about the lambda calculus, you can have the following variant of the theorem:

Theorem B. For any lambda term $t$ there exist a lambda term $s$ such that $t s = s$.

So, this essentially says that any lambda term has a fixed point!

The proof of this variant follows the structure of the original proof:

(1) Let a lambda term $t$ be given.
(2) Let $h = \lambda x . x x$.
(3) Let $k = \lambda x . t(h(x))$. 
(4) We claim that $s = h(k)$ does the job.
(5) By (2) and (4) we have $s = h(k) = k k$.
(6) But by (3) we also have $k k = t(h(k)) = t s$, so we are done.

Note that $k = \lambda x . t ( x x )$. Hence $s = k k = ( \lambda x . t ( x x ) ) ( \lambda x . t ( x x ) )$ 

Therefore, the combination of $h$ and $k$ namely 
$$\phi(f) = ( \lambda x . f ( x x ) ) ( \lambda x . f ( x x ) )$$
in fact gives a fixed point operator: a functional $\phi$ that calculates the fixed point of any given function $f$.