# How to prove the set of Turing machines that accept a string and its mirror is undecidable?

I'm trying to prove the undecidability of the following language.

$$L=\{\langle M \rangle\mid M\text{ is a Turing machine and there is a string }w\\\text{ s.t. }M\text{ accepts }w\text{ and }M\text{ rejects }w'\},$$ where $$w'$$ is the mirrored version of $$w$$.

I know that my first steps should be to find a reduction from $$A_{\text{TM}}$$, which is undecidable but the rejection part of the mirrored string is proving troublesome.

• Be careful with the direction of the reduction. If $P$ is reduced to $Q$, then informally, $P$ is not "harder" than $Q$ and $Q$ is not "easier" than $P$. A reduction from $A_\text{TM}$ to $L$ will be useful if you wanted to show $L$ is undecidable. Apr 2, 2019 at 22:39
• Thank you for pointing that out. However, even though I can see the reduction with the language first part's description, I can't quiet understand how to take into account the part with the mirrored string. Apr 3, 2019 at 8:38
• It looks like you accepted an answer that has an important typo. "Accepts your favourite string and its reverse" is different from "accepts $w$ and rejects its reverse $w'$". I would recommend that you should take some time to verify an answer before accepting it. Note $w=w'$ for some string. Apr 3, 2019 at 14:46

It's the standard reduction from the Halting problem: given a machine $$M$$ and an input $$w$$ to it, construct a new machine $$M$$ that accepts your favourite string and rejects its reverse if $$M(w)$$ halts, and accepts nothing if $$M(w)$$ does not halt.