# Two Turing machines $M_1$ and $M_2$ with $L(M_1) \subseteq L(M_2)$

Suppose $$M_1$$ and $$M_2$$ are two Turing machines such that $$L(M_1)\subseteq L(M_2)$$. Which of the following is true?

• (A) On every input on which $$M_1$$ does not halt, M2 does not halt
• (B) On every input on which $$M_1$$ halts, $$M_2$$ halts too
• (C) On every input which $$M_1$$ accepts, $$M_2$$ halts.
• (D)On every input which $$M_2$$ accepts, $$M_1$$ halts.

I am confused between B and C. This was an online practice test question.

For (B) my claim is that when $$M_1$$ is able to decide the language (i.e., $$M_1$$ halts on every input), then, since it is given $$L(M_1) \subseteq L(M_2)$$, $$M_2$$ should also halt and be able to decide on every input.

However, option (C) also looks convincing. If for every input $$M_1$$ says "yes" in the language, then $$M_2$$ should also be able to decide for that input.

Please let me know how to approach this correctly.

EDIT: After reading the discussion, am I correctly interpreting the problem If I imagine the figure below

SO, (B) must be the wrong choice according to this right?

"Halt" is not synonymous with "accept", although the latter implies the former. A TM can halt and reject. On the other hand, $$L(M)$$ stands for the set of words accepted by $$M$$, not the words it halts for.
Hence, alternative (C) is correct. (B) is incorrect because $$M_1$$ could halt on and reject a word which is accepted by $$M_2$$ (i.e., a word in $$L(M_2) \setminus L(M_1)$$), or for which $$M_2$$ does not halt, even.
Note the question makes little sense, if any, if we assume $$M_1$$ and $$M_2$$ to be deciders since, then, all alternatives are correct, (A) because the premise is always false (since $$M_1$$ always halts) and the others because the respective implications are always true.
• @user3767495 The image appears to depict $M_2$ performing a reduction to $M_1$; I fail to see how this relates to the original question. Do not mistake languages (which are sets) for TMs being used as subroutines! Dec 19 '18 at 8:30