Rice's Theorem is a remarkable and somewhat disturbing result discovered by Henry G. Rice and first presented in his 1953 paper: "Classes of recursively enumerable sets and their decision problems" (Transactions of the American Mathematical Society, volume 74, pp. 358-366). It basically states that any nontrivial index set is undecidable, that is undecidability is not the exception when it comes to recursively enumerable sets, it is the rule. However, the proof is fairly simple. Let P be some index set that is not the null set or the set of all natural numbers. Let j be some description number in P, and let k be some other description number not in P. We may define a function f(x) to be k if x is in P, and j if x is not in P. If we were to suppose that P is a decidable set, then f must be a total recursive function. Then by the first form of the recursion theorem, f must have a fixed point n, such that φn = φf(n). Since n and f(n) are the description numbers of Turing machines that calculate the same partial recursive function, then both these DN's must be either in P or not in P. But this leads to a contradiction, because we defined f so that if x were in P, then f(x) is not in P and vice-versa.

This theorem has many disturbing consequences. A set S is recursively enumerable if it is either the null set or the range of some total recursive function. Any collection C of recursively enumerable sets can thus be reduced to the index set PC = {e | range(φe) is in C }. Thus Rice's theorem basically tells us that if C is not trivial, then it is also undecidable. It cannot be decided for instance whether a recursively enumerable language is empty, finite, actually a regular set, or actually a context-free language, because all of these properties (and practically every other property about a r.e. language that can be imagined) can be reduced into nontrivial index sets.

Rice's Theorem however, doesn't say that everything about Turing machines is undecidable. It only speaks about the structure of the languages that the Turing machine accepts, the r.e. languages, as these yield the index sets the theorem requires. When you start talking about machine-dependent properties, Rice's theorem cannot be used. Examples of machine-dependent properties include questions about whether a particular Turing machine M operates in polynomial time, i.e. for every input word x, M halts within p(|x|) steps, for some polynomial p (this can be shown to be undecidable), or whether some Turing machine N that starts on a blank tape scans any cell more than a certain number of times (this can be shown to be decidable). There are no general results for these types of questions, unfortunately.

Log in or registerto write something here or to contact authors.