Holooly Plus Logo
Holooly Plus Logo

Question 5.7: Show that if A is Turing-recognizable and A ≤m Ā, then A is ...

Show that if A is Turing-recognizable and A\leq _{m} \overline{A}, then A is decidable.

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.

Suppose that A\leq _{m} \overline{A}. Then \overline{A} \leq _{m} A via the same mapping reduction. Because A is Turing-recognizable, Theorem 5.28 implies that \overline{A} is Turing-recognizable, and then Theorem 4.22 implies that A is decidable.

Related Answered Questions

Question: 5.30

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:

(a) INFINITE_{TM} is a language of ...
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.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...