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 \).