209 views

Consider the following statements():

S1: There exists no algorithm for deciding if any two Turing machine M1 and M2 accept the same language

S2:  The problem of determining wether a Turing machine halts on any input is undecidable.

Which of the following option is correct?

1. Both S1 and S2 are correct
2. Both S1 and S2 are  not correct
3. Only Scorrect
4. Only S2  correct

$S_1$ : "There exists no algorithm for deciding if any two Turing machine M1 and M2 accept the same language."

It is the standard "Equivalence problem" for the Recursive Enumerable languages and It is Undecidable. Hence, No Algorithm possible.

$S_2$ : "The problem of determining wether a Turing machine halts on any input is undecidable."

Yes. It is the standard "Halting problem of TM". It is Undecidable and Hence, No Algorithm possible.

0
@deepak seee one toc qsn i hve tagged you..
0
That's not TOC question.