Rice's Theorem - Proof By Kleene's Recursion Theorem

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.