Rice's TheorumWikipedia Reference InformationIn computer science, Rice's theorem named after Henry Gordon Rice (also known as The RiceMyhillShapiro theorem after Rice and John Myhill) is an important result in the theory of computable functions. A property of partial functions is trivial if it holds for all partial computable functions or for none. Rice's theorem states that, for any nontrivial property of partial functions, the question of whether a given algorithm computes a partial function with this property is undecidable. Another way of stating this problem that is more useful in computability theory is this: suppose we have a set of languages S. Then the problem of deciding whether the language of a given Turing machine is in S is undecidable, provided that there exists a Turing machine that recognizes a language in S and a Turing machine that recognizes a language not in S. Effectively this means that there is no machine that can always correctly decide whether the language of a given Turing machine has a particular nontrivial property. Special cases include the undecidability of whether a Turing machine accepts a particular string, whether a Turing machine recognizes a particular recognizable language, and whether the language recognized by a Turing machine could be recognized by a nontrivial simpler machine, such as a finite automaton. The complete, uptodate and editable article about Rice's Theorum can be found at Wikipedia: Rice's Theorum http://en.wikipedia.org/wiki/Rice%27s_theorem
