Proving a language is not Semidecidable

Computer Science Asked by ez ra on December 9, 2020

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.

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 $$wnotin L(M')$$. Thus you can give $$left< M',Mright>$$ as input to $$T$$ and look for its output. If it accept it means that $$L(M')subset L(M)$$ which means $$wnotin L(M)$$.

Answered by Doralisa on December 9, 2020