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.


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.

  • $\begingroup$ I completely agree, I just thought sharing my intuition might help people answering. Thank you very much for the hint, it "clicked" for me. $\endgroup$ – Craig Spurr Nov 10 '13 at 7:00

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.