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:
“I will name you the degrees. The first, the Retort Courteous; the second, the Quip Modest; the third, the Reply Churlish; the fourth, the Reproof Valiant; the fifth, the Countercheck Quarrelsome; the sixth, the Lie with Circumstance; the seventh, the Lie Direct.”
—William Shakespeare (1564–1616)
“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)