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:
“Sculpture and painting are very justly called liberal arts; a lively and strong imagination, together with a just observation, being absolutely necessary to excel in either; which, in my opinion, is by no means the case of music, though called a liberal art, and now in Italy placed even above the other two—a proof of the decline of that country.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)
“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)