0
$\begingroup$

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.

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – John L. Apr 2 '19 at 22:39
  • $\begingroup$ 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. $\endgroup$ – Celestius Apr 3 '19 at 8:38
  • $\begingroup$ 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. $\endgroup$ – John L. Apr 3 '19 at 14:46
0
$\begingroup$

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.

This technique applies to any question of the form "Prove that it's undecidable whether a Turing machine accepts a string or language of some specific kind."

Or just use Rice's theorem, if you've been taught that.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks a lot ! I'll look into Rice's Theorem if I can prove the non-triviality as well as the semantic property. But knowing I indeed haven't been taught it, I'll go with the first proof. $\endgroup$ – Celestius Apr 3 '19 at 12:00

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.