Kleene's Recursion Theorems
Published May 19, 2022 - By Marco Garosi
Two of the most important and fundamental results in computability are those by Stephen Kleene — the so called “recursion theorems” — which were first proved by Kleene himself in 1938. They have profound consequences in the whole field of computability; probably, the two most famous applications are to generate quines and construct fixed points.
A couple of notes about the notation used:
- denotes a Turing Machine;
- denotes the termination of a function (program).
1º Recursion Theorem
Following is what the first recursion theorem states. Let be a total, recursive function.
That is also known as the fixed-point theorem, since it proves there’s a fixed point — namely, .
By applying s-m-n theorem (again, be Kleene) it is possible to fix the first parameter — —, thus building a new function which only takes one variable ( ). The function thus obtained is .
We know, from the premise, that is total and recursive. Function is total recursive as well, thanks to s-m-n theorem. This implies that is also recursive.
This implies that . By substituting (which is a generic Turing Machine, TM) with (which is a specific TM — we have just constructed it), we get .
Let’s define . Then, .
## 2º Recurstion Theorem Following is what the second recursion theorem states. Let be a total recursive function.
By applying s-m-n theorem it is possible to fix the first two parameters — and —, thus getting . The function now has only one variable.
So, . By construction, is total (it always terminates) and recursive (can be implemented as a computer program).
So, total recursive such that:
If we define we get:
(Note that in the proof of the second Recursion Theorem the program has not been included in the notation throughout the steps to lighten the notation — which is already a bit heavy.)