Holooly Plus Logo
Holooly Plus Logo

Question 5.30: Use Rice’s theorem, which appears in Problem 5.28, to prove ...

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

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

The blue check mark means that this solution has been answered and checked by an expert. This guarantees that the final answer is accurate.
Learn more on how we answer questions.

(a) INFINITE_{TM} is a language of TM descriptions. It satisfies the two conditions of Rice’s theorem. First, it is nontrivial because some TMs have infinite languages and others do not. Second, it depends only on the language. If two TMs recognize the same language, either both have descriptions in INFINITE_{TM} or neither do.
Consequently, Rice’s theorem implies that INFINITE_{TM} is undecidable.

Related Answered Questions

Question: 5.28

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 ...

Verified Answer:

Assume for the sake of contradiction that P is a d...
Question: 5.11

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:

Let C = { 〈M〉 | M is a two-tape TM that writes a...
Question: 5.8

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:

You need to handle the case where the head is at t...
Question: 5.7

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

Verified Answer:

Suppose that A\leq _{m} \overline{A}[/latex...
Question: 5.6

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

Verified Answer:

Suppose A \leq _{m} B and B ...
Question: 5.10

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:

Let B = {〈M,w〉 | M is a two-tape TM that writes ...
Question: 5.5

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:

Suppose for a contradiction that A_{TM}\leq...