# Proof that L(M) = {accepts the string 1100 } is undecidable

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?

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

## 1 Answer

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.