Kleene's Recursion Theorem - The Second Recursion Theorem

The Second Recursion Theorem

The second recursion theorem is closely related to definitions of computable functions using recursion. Because it is better known than the first recursion theorem, it is sometimes called just the recursion theorem. Its statement refers to the standard Gödel numbering φ of the partial recursive functions, in which the function corresponding to index e is .

The second recursion theorem. If F is a total computable function then there is an index e such that .

Here means that, for each n, either both and are defined, and their values are equal, or else both are undefined.