and its complement. The class of partial computable functions that are identical to a given partial computable function, and its complement. The class of partial computable functions that diverge (i.e., undefined) for some input, and its complement. The class of indices for computable functions that are total. The class of indices for recursively enumerable sets that are cofinite. The class of indices for recursively enumerable sets that are recursive. 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 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. Assume for contradiction that is 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. Proof by reduction from the halting problem Proof sketch Suppose, for concreteness, that we have an algorithm for examining a program p and determining infallibly whether p is an implementation of the squaring function, which takes an integer d and returns d2. The proof works just as well if we have an algorithm for deciding any other nontrivial property of program behavior (i.e. a semantic and non-trivial property), and is given in general below. The claim is that we can convert our algorithm for identifying squaring programs into one that identifies functions that halt. We will describe an algorithm that takes inputs a and i and determines whether program a halts when given input i. The algorithm for deciding this is conceptually simple: it constructs (the description of) a new program t taking an argument n, which (1) first executes program a on input i (both a and i being hard-coded into the definition of t), and (2) then returns the square of n. If a(i)