0
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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$. $\endgroup$ – Yuval Filmus Nov 4 '20 at 20:09
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.