Which one of the following is not decidable?
1997
Which one 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.
Language generated by a context free grammar is non-empty
Attempted by 3 students.
Show answer & explanation
Correct answer: B
The equivalence problem for Turing machines is undecidable because determining whether two arbitrary TMs accept the same language requires solving the Halting Problem.