0
$\begingroup$

I have the language $L = \{ \langle M_1, M_2 \rangle : L(M_1) \subset L(M_2)\}$ and I'd like to prove that it is not Semidecidable. To do so, I need to use a reduction from $\neg H$. I cannot use Rice's theorem. I'm having a hard time with this, and would appreciate a walkthrough.

$\endgroup$
  • 1
    $\begingroup$ Try fixing one of the machines $M_1,M_2$. $\endgroup$ – Yuval Filmus Nov 28 '19 at 20:56
  • $\begingroup$ @YuvalFilmus The entire class is failing, so needless to say none of us are all that prepared in doing this completely on our own. Would really appreciate a walkthrough on this. $\endgroup$ – ez ra Nov 28 '19 at 22:11
0
$\begingroup$

Using contradiction suppose $L=\{\left< M_1,M_2 \right>|L(M_1)\subset L(M_2)\}$ is semi-decidable. So there exists Turing machine $T$ which for input $\left<M_1,M_2\right>$ if $L(M_1)\subset L(M_2)$ will halt and accept.

We should use this Turing machine $T$ to make another Turing machine $T'$ which halt and accept on input $\left<w,M\right>$ if $M$ doesn't accept $w$. To do so, you have to make another Turing machine $M'$ using $w$ that you are sure $w\notin L(M')$. Thus you can give $\left< M',M\right>$ as input to $T$ and look for its output. If it accept it means that $L(M')\subset L(M)$ which means $w\notin L(M)$.

enter image description here

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Im not sure I see the contradiction: youve said T’ halts if M does not accept w, and you conclude with w is not in the language decided by M (if T’ accepts). Aren’t those statements equivalent? $\endgroup$ – D. Ben Knoble Dec 29 '19 at 14:09
  • $\begingroup$ @D.BenKnoble. We assumed that there exists a "Decidable" Turing machine for $L$ then we were able to make a "Decidable" Turing machine for $HALT^c$ using it. We know that $HALT^c$ isn't decidable so that's the contradiction. $\endgroup$ – Doralisa Dec 30 '19 at 7:04

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.