Michael Sipser Edition 3 Exercise 5 Question 29 (Page No. 241)
in Theory of Computation
224 views
0 votes
0 votes
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
by
635 1320 876
224 views

Subscribe to GO Classes for GATE CSE 2022

Please log in or register to answer this question.

Related questions