Let $$L_\ = \{\langle M\rangle \mid M \text{ is a Turing Machine that accepts the string 1100}\}\, .$$

To proof that the language $L$ is undecidable I should reduce something to $L$, right?

I tried with the classic $A\ TM$, but I could not figure out how to reduce properly.

How I can I proof that $L$ is undecidable?

  • 1
    $\begingroup$ Have you studied Rice's theorem yet? If not, what other tools can you use? $\endgroup$ Oct 19, 2014 at 20:28
  • $\begingroup$ Not yet, I wish to proof that with reductions. $\endgroup$ Oct 19, 2014 at 20:29
  • $\begingroup$ Look up Rice's theorem, and it will give you a template for a reduction for any problem of this form. $\endgroup$ Oct 19, 2014 at 20:29

1 Answer 1


The usual reduction from the halting problem: for example, the same reduction that shows the zero-input halting problem to be undecidable.

Suppose you can determine whether a machine $M$ accepts some magic string (such as $1100$). You can then decide whether an arbitrary machine $M$ halts when given input $x$ as follows. Produce a machine $M_x$ that ignores its input and simulates $M$ running on input $x$. If $M$ halts, $M_x$ accepts whatever input it was given; otherwise, $M$ doesn't halt so nor does the simulation $M_x$. So $M_x$ accepts the magic string if, and only if, $M$ halts on input $x$. Hence, if you could decide whether a machine accepts the magic string, you could decide the halting problem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.