-1

Suppose M1 and M2 are two TMs such that L(M1) = L(M2). Then

(A) On every input on which M1 doesn’t halt, M2 doesn’t halt too.

(B) On every i/p on which M1 halts, M2 halts too.

(C) On every i/p which M1 accepts, M2 halts.

(D) None of above.

My try :

It explained here that M2 accepts strings in L(M1) so definitely it will halt. Other 2 are not guaranteed as Turing machine M does not accept w if it either rejects w by halting to a reject state or loops infinitely on w. Option (C) is the answer.

But, my question is that if equivalence of two Turing Machine is undecidable then how can we decide these given options?

Can you please explain?

It asked here : If M1 and M2 are 2 TM’s such that L(M1) = L(M2) , then which of the following conditions are true? but there were no answers.

Community
  • 1
Mithlesh Upadhyay
  • 4,787
  • I think in this form there are ambiguities, because we do not know whether we are talking about language acceptance or decisiveness. Therefore it could either be in the first case only C, or it could be A,B and C in the latter case. But my memory might not serve me well, rather wait for confirmation or read for yourself here https://cs.stackexchange.com/questions/3554/what-is-the-difference-between-halting-accepting-and-deciding-in-the-context-o. – TStancek Sep 26 '17 at 10:54
  • Why down votes? Please leave comment. – Mithlesh Upadhyay Nov 13 '18 at 09:13

1 Answers1

1

A TM accepts a language if it accepts all strings in the language and does not accept any string not in the language by either rejecting or looping.

$A$ is false because $M_1$ could reject an input by looping while $M_2$ could halt and reject the same input.

$B$ is false because $M_1$ could halt and reject an input while $M_2$ could reject the same input by looping.

$C$ is true because if $M_1$ accepts an input w, $M_2$ must also accept w (since $L(M_1) = L(M_2)$)

user137481
  • 2,605
  • But, here mention that "A Turing machine can either eventually enter an accepting state, enter a rejecting state, or loop forever. If it enters either an accepting or rejecting state, then it halts." – Mithlesh Upadhyay Sep 28 '17 at 05:34
  • That is correct. So, the TM can either halt and accept, halt and reject or loop. The "halt and reject" and "loop" are considered "reject" states. So, suppose $M_1$ rejects input $w$ by looping. $M2$ can however reject and halt on input $w$. That's why A is false. By reversing the argument, that is why B is also false. – user137481 Sep 28 '17 at 14:29
  • Thanks for nice explanation. – Mithlesh Upadhyay Oct 03 '17 at 05:42