Proof By Kleene's Recursion Theorem
A corollary to Kleene's recursion theorem states that for every Gödel numbering of the computable functions and every computable function, there is an index such that returns . (In the following, we will say that "returns" if either, or both and are undefined.) Intuitively, is a quine, a function that returns its own source code (Gödel number), except that rather than returning it directly, passes its Gödel number to and returns the result.
Let be a set of computable functions such that . Then there are computable functions and . Suppose that the set of indices such that is decidable; then, there exists a function that returns if, and otherwise. By the corollary to the recursion theorem, there is an index such that returns . But then, if, then is the same function as, and therefore ; and if, then is, and therefore . In both cases, we have a contradiction.
Read more about this topic: Rice's Theorem
Famous quotes containing the words proof and/or theorem:
“The thing with Catholicism, the same as all religions, is that it teaches what should be, which seems rather incorrect. This is “what should be.” Now, if you’re taught to live up to a “what should be” that never existed—only an occult superstition, no proof of this “should be”Mthen you can sit on a jury and indict easily, you can cast the first stone, you can burn Adolf Eichmann, like that!”
—Lenny Bruce (1925–1966)
“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)