Undecidability of closure under reverse of language accepted by TM

Question

Prove that the following problem is undecidable using a reduction: Given a Turing machine $S$, does $S$ accept a word $w$ iff it accepts its reverse $w^R$?

There is a solution here, which I don't understand. We reduce from the halting problem. Given a Turing machine $M$ and a word $w$, we construct a Turing machine $M_1$:

M1(x) =
   simulate M on w
   if M accepts w
      if x = 01
         accept

The machine $M_1$ accepts only 01 and all other strings will be rejected. Then

MA(<M>, w) = 
   Construct M1 as above
   if ML accepts <M1>
      reject
   else if ML rejects <M1>
      accept

so the Turing machine $S$ will accept all strings except $w=01$.

Why is the string 01 the only string which is accepted by $M_1$? Why it cannot be 10 instead of 01, for example? It doesn't make sense to me.

If $w$ were 01 and $L$ would also contain 10 and 01, then it should also be accepted, no?

Would anyone please explain me the whole process and especially the Turing machine $M_1$? Why does this work?

Answer 1

Ok , first consider this clearer proof which takes a similar approach :

Assume S is decidable , we show a reduction ATM ≤m S , obtaining a contradiction

We map <M,w> to <M'> such that :

M' = " on input x :

If x = 01 accept ,

If x = 10 reject ,

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

Now , if M accepts w , meaning <M,w> ∈ ATM , then the L(M') would be = {01 (which is always accepted) , 10 (which is only accepted if M accepts w) } and thus <M'> ∈ S

If M rejects w or loops on w , meaning <M,w> does not belong to ATM , then L(M') = {01} and thus <M'> does not belong to S , completing our reduction , and thus if S is decidable ATM is decidable which is a contradiction , thus S is undecidable

The point is to construct M' such that it accepts a string and it's reverse if M accepts w so that also S accepts M' or accept a single string if M rejects w so S rejects M' since M' doesn't also accept the reverse of the string

You could have used any 2 different strings as long as one is the reverse of the other , instead of 01,10 feel free to use 110,011 hopefully you get the point

Following the link the reduction is from ATM , the only difference is that if M accepts w , then L(M') is ∅ so S accepts M' and if M rejects w or loops on w L(M) = {01 (which could have been chosen to be any string) } and thus M' does not belong to S

Finally it's worth reminding that ATM is the language where M accepts w , while Halting is the language where M halts on w , you may find it a good exercise to try showing a reduction from Halting to S , the proof would be very similar