**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:

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

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

## 1 comment:

Wikipedia says that Jan Willem Klop constructed the fixed point combinator

LLL...L(26 times) whereL:= λabcdefghijklmnopqstuvwxyzr.(r(this is a fixed point combinator)).Post a Comment