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:
“Behind every individual closes organization; before him opens liberty,—the Better, the Best. The first and worse races are dead. The second and imperfect races are dying out, or remain for the maturing of the higher. In the latest race, in man, every generosity, every new perception, the love and praise he extorts from his fellows, are certificates of advance out of fate into freedom.”
—Ralph Waldo Emerson (1803–1882)
“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)