Problem Detail: Let $text{NOT-SELF} = {langle M rangle : M text{ is a TM that does not accept } langle M rangle }$. How do you prove the following claim?
If $Q$ is a TM so that $L(Q) subseteq text{NOT-SELF}$, prove that $langle Q rangle in text{NOT-SELF}$.
Asked By : user2977105
Answered By : Yuval Filmus
Hint: If $langle Q rangle notin text{NOT-SELF}$ then $langle Q rangle notin L(Q)$, and so $langle Q rangle in text{NOT-SELF}$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/17882
