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.
2.9.0.26 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
by 2.6.0.38
Take e = (a, a). □ ...
Get Theory of Computation now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
