Let T = { | M is a TM that accepts $w^R$ whenever it accepts w}. Show that T is undecidable

Question

Let T = {<M> | M is a TM that accepts w^r whenever it accepts w}.
Show that T is undecidable.

I have two answers to this question - San Diego:

5.9
Let T = { <M> | M is a TM that accepts w^r whenever it accepts w }.

Assume T is decidable and let decider R decide T. Reduce from A_TM by constructing a TM S as follows:

S: on input <M,w>

create a TM Q as follows:
On input x:

if x does not have the form 01 or 10 reject.

if x has the form 01, then accept.

else (x has the form 10), Run M on w and accept if M accepts w.

Run R on

Accept if R accepts, reject if R rejects.

Because S decides A_TM, which is known to be undecidable, we then know that T is not decidable

Undisclosed source:

5.12 We show that A_TM ≤_m S by mapping ‹M, w› to ‹M'› where M' is the following TM:

M' = “On input x:

If x = 01 then accept.

If x ≠ 10 then reject.

If x = 10 simulate M on w.
If M accepts w then accept; if M halts and rejects then reject.”

If ‹M, w› ∈ A_TM then M accepts w and L(M') = {01,10}, so ‹M'› ∈ S.
Conversely, if ‹M, w› ∉ A_TM then L(M') = {01}, so ‹M'› ∉ S. Therefore,
‹M, w› ∈ A_TM ⇔ ‹M'› ∈ S.

But I do not understand the following:

1- what is the relation between x and w?

2- why we consider the 2 cases ‹M, w› ∈ A_TM and ‹M, w› ∉ A_TM?

3- why if A is mapping reducible to S this makes S undecidable?

could anyone clarify these points for me?

Please do not post text or code as an image; it's not searchable and can't be interpreted by screen readers. (You can use html entities for mathematical symbols.) — m69's been on strike for years, May 04 '18 at 22:48
Your question is incomplete. What's R, and what does $w^R$ mean? What's $A_{TM}$? Is it the same as $T$? — Paul Hankin, May 06 '18 at 07:24
@PaulHankin R means the reverse of the string which means the same letters of the string written in reverse order. — Intuition, May 06 '18 at 23:35
@m69 okay I am sorry, sometimes I do not have enough time to write my question .....I am so sorry. — Intuition, May 06 '18 at 23:36

Ali Soltani · Accepted Answer · 2018-05-09T09:54:59.667

I think it is not suitable for asking in SO because it is not a educational website, but I answered it.

1- what is the relation between x and w?

Answer 1: x is a symbol that used for using a symbol for operate. This symbol should not be in alphabet of language, just it. It hasn't any relation to w.

2- why we consider the 2 cases ‹M, w› ∈ ATM and ‹M, w› ∉ ATM?

Answer 2: For proofing a language like L is decidable or not, we need to determine a string like w is member of language or not. So we have to consider two type of string w∉L and w∈L.

3- why if A is mapping reducible to S this makes S undecidable?

Answer 3: It means the process of checking a string is in language in A and S is similar and if we can't find a algorithm for checking this for A, we can't find any algorithm for S.

Let T = { | M is a TM that accepts $w^R$ whenever it accepts w}. Show that T is undecidable

1 Answers1