Im working on a problem for a homework assignment in finite automata, but I'm having trouble conceptually grasping the problem in the first place.

Prove that the following is undecidable: $SUB_{TM} = \{\langle M_1,M_2 \rangle \mid L(M_1) \subseteq L(M_2)\}$

I'm not sure what kind of Turing machine $SUB_{TM}$ is even describing. Can anyone help me conceptually understand this problem or possibly give me any hints? I would of course cite this post in my homework submission. Thank you.


$SUB_{TM}$ is the problem (language) of deciding whether for two given turing machines $M_1$ and $M_2$, we have that $L(M_1)\subseteq L(M_2)$.

Your task is to show that this language is undecidable - there is no turing machine that decides $SUB_{TM}$.

  • $\begingroup$ As silly as the question this was, this answer was actually really helpful. I understand the basic definition format in most contexts but was thrown off for a couple of typos in the early version of the assignment and thought it was a turning machine I was supposed to be familiar with. Thanks! $\endgroup$
    – zaserman
    Dec 2 '21 at 3:09
  • $\begingroup$ Glad I can help! The question was not silly at all ;) $\endgroup$
    – nir shahar
    Dec 2 '21 at 10:12

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.