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.
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)$)