The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
170 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
asked in Theory of Computation by (283 points) | 170 views

1 Answer

0 votes

Answer : 1

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

 

answered by Boss (16.6k points)
0
@deepak seee one toc qsn i hve tagged you..
0
That's not TOC question.

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

36,995 questions
44,571 answers
126,781 comments
43,637 users