# 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
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.