The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
312 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 Junior (901 points) | 312 views

1 Answer

+1 vote
Best answer

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 (20.7k points)
selected by
0
@deepak seee one toc qsn i hve tagged you..
0
That's not TOC question.

Related questions

0 votes
1 answer
1
asked Jul 11 in Theory of Computation by Sanjay Sharma Veteran (50k points) | 137 views


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

44,237 questions
49,719 answers
163,894 comments
65,834 users