@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

0 votes

**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.4k
- Engineering Mathematics 5.7k
- Digital Logic 2.2k
- Programming & DS 4.1k
- Algorithms 3.6k
- Theory of Computation 4.5k
- Compiler Design 1.7k
- Databases 3.2k
- CO & Architecture 2.8k
- Computer Networks 3.2k
- Non GATE 1.1k
- Others 1.5k
- Admissions 503
- Exam Queries 474
- Tier 1 Placement Questions 22
- Job Queries 61
- Projects 13

39,754 questions

46,768 answers

140,672 comments

58,550 users