# Proving a language is not Semidecidable

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.

• Try fixing one of the machines $M_1,M_2$. Nov 28 '19 at 20:56
• @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. Nov 28 '19 at 22:11

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$$ 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$$ 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)$$.
• @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. Dec 30 '19 at 7:04