# Undecidability of closure under reverse of language accepted by TM

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?

• I found it very hard to understand this question. You are defining a machine $M_A$ using the undefined $M_L$, and then you are referring to $S$. What is the relation between these machines? Also, you didn't bother to describe the structure of the argument – I added some details, but I still do not understand your remarks following the definition of $M_A$. – Yuval Filmus Nov 4 '20 at 20:09

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