0
$\begingroup$

$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$?

$\endgroup$
  • $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – Evil Oct 22 '19 at 0:31
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Your regex for $L_1$ doesn't seem to be correct, it should be something like $0^*1(1\mid0)^*)$. $\endgroup$ – siracusa Oct 23 '19 at 6:51
  • 1
    $\begingroup$ You can see previous version of question it has $L_1$ defined as follow. $L_1 = \{w\in\{0, 1\}^* |\text{ w is a sequence of one or more 1's}\}$. And here is a link to that version. $\endgroup$ – Vimal Patel Oct 23 '19 at 7:05

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.