Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Rice's theorem
Summary
In computability theory, Rice's theorem states that all non-trivial semantic properties of programs are undecidable. A semantic property is one about the program's behavior (for instance, does the program terminate for all inputs), unlike a syntactic property (for instance, does the program contain an if-then-else statement). A property is non-trivial if it is neither true for every partial computable function, nor false for every partial computable function.
Rice's theorem can also be put in terms of functions: for any non-trivial property of partial functions, no general and effective method can decide whether an algorithm computes a partial function with that property. Here, a property of partial functions is called trivial if it holds for all partial computable functions or for none, and an effective decision method is called general if it decides correctly for every algorithm. The theorem is named after Henry Gordon Rice, who proved it in his doctoral dissertation of 1951 at Syracuse University.
Let be a property of a formal language that is nontrivial, meaning
there exists a recursively enumerable language having the property p,
there exists a recursively enumerable language not having the property p,
(that is, p is neither uniformly true nor uniformly false for all recursively enumerable languages).
Then it is undecidable to determine for a given Turing machine M, whether the language recognized by it has the property p.
In practice, this means that there is no machine that can always decide whether the language of a given Turing machine has a particular nontrivial property. Special cases include e.g. the undecidability of whether the language recognized by a Turing machine could be recognized by a nontrivial simpler machine, such as a finite automaton (meaning, it is undecidable whether the language of a Turing machine is regular).
It is important to note that Rice's theorem does not concern the properties of machines or programs; it concerns properties of functions and languages.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.