search
Log In
0 votes
37 views
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 $\langle M_{1}\rangle \in P$ iff $\langle M_{2}\rangle \in P$ . Here, $M_{1}$ and $M_{2}$ are any $TMs$. Prove that $P$ is an undecidable language.

Show that both conditions are necessary for proving that $P$ is undecidable.
in Theory of Computation 37 views

Please log in or register to answer this question.

Related questions

1 vote
0 answers
1
66 views
Use Rice’s theorem, to prove the undecidability of each of the following languages. $INFINITE_{TM} = \{\langle M \rangle \mid \text{M is a TM and L(M) is an infinite language}\}$. $\{\langle M \rangle \mid \text{M is a TM and }\:1011 \in L(M)\}$. $ ALL_{TM} = \{\langle M \rangle \mid \text{ M is a TM and}\: L(M) = Σ^{\ast} \}$.
asked Oct 20, 2019 in Theory of Computation Lakshman Patel RJIT 66 views
0 votes
0 answers
2
51 views
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$ ... $M_{1}$ and $M_{2}$ are any $TMs$. Prove that $P$ is an undecidable language.
asked Oct 20, 2019 in Theory of Computation Lakshman Patel RJIT 51 views
0 votes
1 answer
3
0 votes
0 answers
4
87 views
Prove that the following two languages are undecidable. $OVERLAP_{CFG} = \{\langle G, H\rangle \mid \text{G and H are CFGs where}\: L(G) \cap L(H) \neq \emptyset\}$. $PREFIX-FREE_{CFG} = \{\langle G \rangle \mid \text{G is a CFG where L(G) is prefix-free}\}$.
asked Oct 20, 2019 in Theory of Computation Lakshman Patel RJIT 87 views
...