1
$\begingroup$

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

enter image description here

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

$\endgroup$

1 Answer 1

1
$\begingroup$

"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.

$\endgroup$
4
  • $\begingroup$ Please check whether the image I have added, is correct as per my understanding of the problem. $\endgroup$ Commented Dec 19, 2018 at 7:36
  • 1
    $\begingroup$ @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! $\endgroup$
    – dkaeae
    Commented Dec 19, 2018 at 8:30
  • $\begingroup$ ohhhh. Got it.Thank you so much,I learned something because of you $\endgroup$ Commented Dec 20, 2018 at 6:27
  • $\begingroup$ @user3767495 Glad to be of help. If you think this post answers your question, then don't forget to upvote and mark it as an "accepted" answer by clicking the tick mark to the left :) $\endgroup$
    – dkaeae
    Commented Dec 20, 2018 at 7:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.