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 O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.