Kleene’s Recursion Theorem: A Proof for Beginners

Here we give an illustrative proof of Kleene’s recursion theorem, a fundamental theorem in computability/recursion theory. The proof is so simple it can be stated in few lines. On the other hand, the proof is a beauty in itself (after you get hold of it). Without further ado, we will first state the preliminary definitions/lemmas/theorems and then give the formal statement.

Continue reading “Kleene’s Recursion Theorem: A Proof for Beginners”

Advertisements