2.9 THE RECURSION THEOREM
The recursion theorem, by that name, is due to Kleene but owes its existence (and proof) to the work of Gödel (1931) on the incompleteness phenomenon. We look at few versions of this very powerful tool in what follows, and then come back to this comment regarding the connection with Gödel’s work.
18.104.22.168 Theorem. (Kleene’s Recursion Theorem) If z.f (z, n) , then for some e, we have (n) ⋍ f (e, n), for all n.
Proof. Let . Then
Take e = (a, a). □ ...