TransWikia.com

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.

One Answer

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_2right>$ 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,Mright>$ 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)$.

enter image description here

Answered by Doralisa on December 9, 2020

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP