CampusProgram.com: University, College and Employment Resources that Guide you from High School to your Dream Job.

MENUHomeUniversitiesCollegesProgramsJobsLibraryArticlesStore
Google
 
Web www.campusprogram.com

Rice's Theorum

Wikipedia Reference Information

In computer science, Rice's theorem named after Henry Gordon Rice (also known as The Rice-Myhill-Shapiro 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 non-trivial 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, up-to-date and editable article about Rice's Theorum can be found at Wikipedia: Rice's Theorum
http://en.wikipedia.org/wiki/Rice%27s_theorem




MENUHomeUniversitiesCollegesProgramsJobsLibraryArticlesStore
Google
 
Web www.campusprogram.com

Copyright 1996-2007 - CampusProgram.com