I've been thinking about this one for a while:Consider the language of TMs which do not recognize themselves: $L_{s}=\{ \langle M\rangle ~|~ M \text{ does not accept } \langle M\rangle \}$. If $N$ is a TM where $L(N) \subseteq L_s$, then is $\langle N\rangle \in L_s$?Intuitively, I'm pretty sure it is true. I pictured $N$ as a compiler, and imagined some machine $P$ that $N$ compiled. It seemed that if $P$ was not able to bootstrap, then $N$ wouldn't be able to either. But I'm having trouble thinking about this problem more formally. Am I on the right track? A hint would be really helpful.
If the language of a TM is TMs which cannot self recognize, can the original TM?
formal languages;turing machines
You have to argue formally. Intuition can be helpful in pointing the way, but you need a formal argument in the end.Hint: Suppose that $\langle N \rangle \notin L_s$. Then $N$ accepts $\langle N \rangle$, and so $\langle N \rangle \in L(N) \subseteq L_s$, a contradiction.