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