1
$\begingroup$

Let $L = \{\langle M \rangle \mid \text{M is a TM which accepts only the string "010"}\}$. Prove that $L$ is undecidable.

This is my solution, reducing $A_{TM}$ to $L$:

$R(\langle M,w \rangle)$ outputs $M'(x)$, such that:

if $(x == "010")$: run $M$ on $w$ and do on $x$ what $M$ does on $w$

else reject $x$

The language $L(M')=\{010\} \iff M$ accepts $w$. Is the mapping reduction well done? Thank you.

| cite | improve this question | |
$\endgroup$
  • 2
    $\begingroup$ Welcome to the site! That said, we typically don't like "check my result" questions, if for no other reason than the fact that the answer would be of no help to later viewers of your question. [By the way, your answer is correct, but you don't need the else clause.] $\endgroup$ – Rick Decker Dec 20 '16 at 18:39
  • $\begingroup$ Thank you. Why I don't need the else clause? You mean it is superfluous? $\endgroup$ – MoreOver Dec 20 '16 at 18:53
  • 1
    $\begingroup$ Correct. Try running $M'$ without the else clause. Running $M$ on $w$ will result in either (1) $M$ accepts $w$, in which case $L(M')=\{010\}$, (2) $M$ halts, but not in the accept state, in which case $M'$ will not accept anything (so you don't need the else clause), or (3) $M$ will run forever without entering the accept state, in which case you'll never get to the else part. $\endgroup$ – Rick Decker Dec 20 '16 at 19:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.