1
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ Nice question! What are your thoughts? Have you attempted to prove it? $\endgroup$ – Yuval Filmus Mar 25 '18 at 13:10
  • 1
    $\begingroup$ 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. $\endgroup$ – D.W. Mar 25 '18 at 15:51
0
$\begingroup$

Hint

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

Complete answer

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.

$\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.