@deepak seee one toc qsn i hve tagged you..

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

0 votes

Consider the following statements():

S_{1}: There exists no algorithm for deciding if any two Turing machine M_{1} and M_{2} accept the same language

S_{2}: The problem of determining wether a Turing machine halts on any input is undecidable.

Which of the following option is **correct**?

- Both S
_{1}and S_{2}are correct - Both S
_{1}and S_{2}are not correct - Only S
_{1 }correct - Only S2
_{ }correct

+1 vote

Best answer

**Answer : 1**

$S_1$ : "There exists no algorithm for deciding if any two Turing machine M_{1} and M_{2} 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.

- All categories
- General Aptitude 1.5k
- Engineering Mathematics 7.3k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.4k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 568
- Exam Queries 566
- Tier 1 Placement Questions 23
- Job Queries 69
- Projects 18

48,450 questions

52,747 answers

183,347 comments

68,219 users