[Solved]: Proof that L(M) = {accepts the string 1100 } is undecidable

Problem Detail: 

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?

Asked By : Rafael Castro

Answered By : David Richerby

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/32095

3.2K people like this

 Download Related Notes/Documents