Which of the following is not decidable?
1997
Which of the following is not decidable?
- A.
Given a Turing machine M, a string s and an integer k, M accepts s within k steps
- B.
Equivalence of two given Turing machines
- C.
Language accepted by a given finite state machine is not empty
- D.
Languages generated by a context free grammar is non empty
Attempted by 7 students.
Show answer & explanation
Correct answer: B
To determine decidability, we analyze each problem. Simulating a Turing machine for fixed steps always halts, making it decidable. Checking emptiness for Finite State Machines and Context-Free Grammars is also algorithmically solvable. However, determining if two Turing machines accept the same language is undecidable, as it can be reduced from the Halting Problem.
A video solution is available for this question — log in and enroll to watch it.