Question 5.28: Rice’s theorem. Let P be any nontrivial property of the lang...
Rice’s theorem. Let P be any nontrivial property of the language of a Turing machine. Prove that the problem of determining whether a given Turing machine’s language has property P is undecidable.
In more formal terms, let P be a language consisting of Turing machine descriptions where P fulfills two conditions. First, P is nontrivial—it contains some, but not all, TM descriptions. Second, P is a property of the TM’s language—whenever
L (M_{1}) = L (M_{2} ), we have 〈M_{1}〉 ∈ P iff 〈M_{2}〉 ∈ P. Here, M_{1} and M_{2} are any
TMs. Prove that P is an undecidable language.
Assume for the sake of contradiction that P is a decidable language satisfying the properties and let R_{P} be a TM that decides P. We show how to decide A_{TM} using R_{P} by constructing TM S. First, let T_{\emptyset } be a TM that always rejects, so L (T_{\emptyset })=\emptyset.
You may assume that 〈T_{\emptyset }〉 ∉ P without loss of generality because you could proceed with \overline{P} instead of P if 〈T_{\emptyset }〉 ∈ P.
Because P is not trivial, there exists a TM T with 〈 T 〉 ∈ P. Design S to decide A_{TM} using R_{P}’s ability to distinguish between T_{\emptyset } and T.
S = “On input 〈M,w〉:
1. Use M and w to construct the following TM M_{w}.
M_{w} = “On input x:
1. Simulate M on w. If it halts and rejects, reject .
If it accepts, proceed to stage 2.
2. Simulate T on x. If it accepts, accept .”
2. Use TM R_{P} to determine whether 〈Mw〉 ∈ P. If YES, accept .
If NO, reject .”
TM M_{w} simulates T if M accepts w. Hence L (M_{w}) equals L(T ) if M accepts w and \emptyset otherwise. Therefore, 〈Mw〉 ∈ P iff M accepts w.