RICE’S THEOREM: A Turing machine (TM) is a way to describe a language and the decision problem can be interpreted as belonging to the general class of problems:
“Given a Turing machine, does L(TM) have the property P”? In this case P is the property of containing the null string.
THEOREM: “If P is a property of languages that is satisfied by some but not all recursively enumerable languages, then the decision problem. D: Given a TM, does L(TM) have property P is unsolvable.”
Proof:Assume that P is a nontrivial language property. Starting with Turing machine TM, an arbitrary instance of Accepts (Ù). (Which is the other unsolvable problem), we need to find an instance TM¢ of D so that the answer for TM and TM¢ are the same.
-
The machine TM' is constructed so that the first things it does it to move its tape head past the input string and execute TM on inputÙ. What TM¢ does with its original input after that depends on the outcome of Accepts (Ù). We would like TM' to proceed with its original input as if its goal were to accept some original input as if its goal were to accept some language LA so that it halts if and only if the original input is in LA. Also we would want TM¢ to proceed as if it were accepted as a different language L.
-
In order to get everything right, we want LA to be a language satisfying P and LB to be a language not satisfying P and LB to be a language not satisfyingP. This ensures that if TM' is a yes-instance of D if and only if TM is ayes-instance of Accepts (Ù).
-
The problem that exists here is that if TM does not acceptÙ, then it will go into infinite loop. Then TM¢ could not accept anything. Therefore LB is an empty language. Therefore if TM crashed on inputÙ, then TM¢ also crashes. If Æ happens to be a language not satisfying the property P, then we have exactly what we want.
-
The choice of the language LA is arbitrary subject to the condition LA must satisfy P; then we have such a language LA, since P is nontrival.
-
Therefore it is proved that if P is any nontrivial property not satisfied by the empty language, then D is unsolvable, which proves the Rice’s Theorem.
