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 ImageszImages.f (z, Imagesn) images Images, then for some e, we have Images (Imagesn) ⋍ f (e, Imagesn), for all Imagesn.

Proof. Let Images. 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.