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

Question

[latex]L (M_{1}) = L (M_{2} )[/latex], we have 〈[latex]M_{1}[/latex]〉 ∈ P iff 〈[latex]M_{2}[/latex]〉 ∈ P. Here, [latex]M_{1}[/latex] and [latex]M_{2}[/latex] are any
TMs. Prove that P is an undecidable language.

Accepted Answer

Assume for the sake of contradiction that P is a decidable language satisfying the properties and let [latex]R_{P}[/latex] be a TM that decides P. We show how to decide [latex]A_{TM}[/latex] using [latex]R_{P}[/latex] by constructing TM S. First, let [latex]T_{\emptyset }[/latex] be a TM that always rejects, so [latex]L (T_{\emptyset })=\emptyset[/latex].

You may assume that 〈[latex]T_{\emptyset }[/latex]〉 ∉ P without loss of generality because you could proceed with [latex]\overline{P}[/latex] instead of P if 〈[latex]T_{\emptyset }[/latex]〉 ∈ P.

Because P is not trivial, there exists a TM T with 〈 T 〉 ∈ P. Design S to decide [latex]A_{TM}[/latex] using [latex]R_{P}[/latex]’s ability to distinguish between [latex]T_{\emptyset }[/latex] and T.

S = “On input 〈M,w〉:
1. Use M and w to construct the following TM [latex]M_{w}[/latex].

[latex]M_{w}[/latex] = “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 [latex]R_{P}[/latex] to determine whether 〈Mw〉 ∈ P. If YES, accept .
If NO, reject .”

TM [latex]M_{w}[/latex] simulates T if M accepts w. Hence L ([latex]M_{w}[/latex]) equals L(T ) if M accepts w and [latex]\emptyset[/latex] otherwise. Therefore, 〈Mw〉 ∈ P iff M accepts w.

Question 5.28: Rice’s theorem. Let P be any nontrivial property of the lang...

Related Answered Questions

Use Rice’s theorem, which appears in Problem 5.28, to prove the undecidability of each of the following languages. a. INFINITETM = {〈M〉 | M is a TM and L(M) is an infinite language}. ...

Verified Answer:

Consider the problem of determining whether a two-tape Turing machine ever writes a nonblank symbol on its second tape during the course of its computation on any input string. Formulate this problem as a language and show that it is undecidable. ...

Verified Answer:

In the proof of Theorem 5.15, we modified the Turing machine M so that it never tries to move its head off the left-hand end of the tape. Suppose that we did not make this modification to M. Modify the PCP construction to handle this case. ...

Verified Answer:

Show that if A is Turing-recognizable and A ≤m Ā, then A is decidable. ...

Verified Answer:

Show that ≤m is a transitive relation. ...

Verified Answer:

Consider the problem of determining whether a two-tape Turing machine ever writes a nonblank symbol on its second tape when it is run on input w. Formulate this problem as a language and show that it is undecidable. ...

Verified Answer:

Show that ATM is not mapping reducible to ETM. In other words, show that no computable function reduces ATM to ETM. (Hint: Use a proof by contradiction, and facts you already know about ATM and ETM.) ...

Verified Answer: