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. Introduction 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. For example, whether a machine runs for more than 100 steps on a particular input is a decidable property, even though it is non-trivial. Two different machines recognizing exactly the same language might require a different number of steps to recognize the same input string. Similarly, whether a machine has more than five states is a decidable property of the machine, as the number of states can simply be counted. For properties of this kind, which concerns a Turing machine but not