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.
Read more about this topic: Kleene's Recursion Theorem
Famous quotes containing the words the second and/or theorem:
“Three elements go to make up an idea. The first is its intrinsic quality as a feeling. The second is the energy with which it affects other ideas, an energy which is infinite in the here-and-nowness of immediate sensation, finite and relative in the recency of the past. The third element is the tendency of an idea to bring along other ideas with it.”
—Charles Sanders Peirce (1839–1914)
“To insure the adoration of a theorem for any length of time, faith is not enough, a police force is needed as well.”
—Albert Camus (1913–1960)