Use Rices theorem, which appears in Problem 5.28, to prove the undecidability of each of the following

Question:

Use Rice’s theorem, which appears in Problem 5.28, to prove the undecidability of each of the following languages.

Aa. INFINITETM = {〈M〉| M is a TM and L(M) is an infinite language}.

b. {〈M〉| M is a TM and 1011 ∈ L(M)}.

c. ALLTM = {〈M〉| M is a TM and L(M) = Σ*}.


Problem 5.28

Let P be any nontrivial property of the language of a Turing machine. Prove that the problem of determining whether a given Turingmachine’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(M1) = L(M2), we have 〈M1〉 ∈ P iff 〈M2〉 ∈ P. Here, M1 and M2 are any TMs. Prove that P is an undecidable language.

Fantastic news! We've Found the answer you've been seeking!

Step by Step Answer:

Related Book For  book-img-for-question
Question Posted: