## Tuesday, 18 December 2012

### 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$$.