1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Have you studied Rice's theorem yet? If not, what other tools can you use? $\endgroup$ – Gilles Oct 19 '14 at 20:28
  • $\begingroup$ Not yet, I wish to proof that with reductions. $\endgroup$ – Rafael Castro Oct 19 '14 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$ – jmite Oct 19 '14 at 20:29
0
$\begingroup$

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.

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