Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
$L_1$ = A sequence of $0$ or $1$'s such that at least one $1$ is in the sequence
$L_2$ = Turing machines that decide $L_1$
I think the first language is decideable, as the input string is of finite length and you can check every character in the string.
However, my intuition says the second language is undecideable. This would be like checking if a TM is equal to a TM that decides $L_1$.
Am I correct? And if so, how should I proceed to reduce the halting problem to $L_2$?
Original Question:
$L_1 = \{w \in \{0|1\}^* | \text{ w is a sequence of one or more 1's } \}$
$L_2 = \{\langle M \rangle | \text{ Turing machine } M \text{ decides } L \}$
prove that $L_2$ is undecidable.
Answer:
For first part you are correct. First language $L_1$ is indeed decidable. Actually it is regular as represented by regular expression $1^+$.
Now coming to second one $L_2$. This language is as you said undecidable. And you can prove it by reducing halting problem which is known to be undecidable to this problem.
For doing this you have to create an instance of problem in question such that solving it gives us solution of halting problem.
Now formally we can define turing machine $\tau\langle M, w\rangle =M'$. Where $M'$ is a turing machine which started on input $x$ checks if $x$ is of form $1^+$. If no then it rejct it immediately. Otherwise it erases $x$ from it's tape then copies $M$ and $w$ on its tape and simulates $M$ on $w$. If $M$ stops then it accepts $x$(which it have erased).
Proof of validity of reduction:
$M$ halts on $w$ $\implies$ $M'$ accepts all and only strings of form $1^+$.
$M$ does not halt on $w$ $\implies$ $M'$ accepts empty set. In particular it does not accept strings of form $1^+$.
So now if there would be any turing machine that decides $L_2$ then we can use it to find whether $M'\in L_2$ or not? If it outputs yes then we infer that original $M$ halts on $w$. Otherwise we infer that $M$ does not halt on $w$.
And because we know that halting problem is undecidable we conclude that no such turing machine exists which can decide $L_2$ and consequently $L_2$ is undecidable.
Hence proved.
