0
$\begingroup$

I've done some other problems by reduction, but I'm quite stuck here. I'm not really sure what to do with $M'$. I know that because $L(M) \nsubseteq L(M')$ there exists $w \in L(M)$ and $w \notin L(M')$ and I'm trying to create the machine that ignores the input and accepts only when M accepts $w$, but I'm kinda stuck on what to do next. Any suggestions?

$\endgroup$
1
$\begingroup$

Don't be confused by this question. Instead of studying $L^{\nsubseteq}_{M'}=\{ \langle M \rangle \ | \ L(M) \nsubseteq L(M')\}$ you might consider as well the language $L_G=\{ \langle M \rangle \ | \ L(M) \nsubseteq G\}$ for $G$ being any language. It is important to notice that there is always a Turing machines $M$ with $\langle M \rangle \in L_G$ but always a machine $M'$ with $\langle M' \rangle \not \in L_G$. So you are looking for a nontrivial set of Turing machines. This allows you to apply Rice's theorem and you are done.

If you want to get a proof via reduction just look in the proof of Rice's theorem. It shows you how to get a generic reduction for these cases.

$\endgroup$
0

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.