# Reduce ATM to the language of TM encodings concatenated by a string where the TM accepts both the string and its reverse

Prove that the language $LM =\{\langle M,x\rangle\mid \ M \text{ accepts }x\text{ and rev}(x) \}$, where $\mathrm{rev}(x)$ is the reverse of the string $x$, is undecidable with a reduction from $A_{\mathrm{TM}}$. Note that the empty string belongs to $LM$.

• Nice question! What are your thoughts? Have you attempted to prove it? – Yuval Filmus Mar 25 '18 at 13:10
• Have you made any attempt yourself? Can you show us what progress you made and where you got stuck? Do you have any specific question about this exercise? Is there some concept you don't understand? Or are you just asking us to solve the exercise for you? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. – D.W. Mar 25 '18 at 15:51

Forget the similarity between $$LM$$ and $$A_{\mathrm{TM}}$$, and for an input $$\langle M,x\rangle$$ of the reduction, try to build a new TM $$N$$ such that $$M$$ accepts $$x$$ if and only if $$N$$ accepts $$0$$, i.e. $$\langle N,0\rangle\in LM$$.
Given $$\langle M,x\rangle$$, build a TM $$N_{M,x}$$ that on any input always simulates $$M$$ on $$x$$. Therefore if $$M$$ accepts $$x$$, $$N_{M,x}$$ accepts everything, otherwise $$N_{M,x}$$ rejects anything. Now we can see $$M$$ accepts $$x$$ if and only if $$N_{M,x}$$ accepts $$0$$, i.e. $$\langle N_{M,x},0\rangle\in LM$$. All above completes the reduction.