Which one of the following is not decidable?
A)given a Turing machine M, a string s, and an integer k, M accepts s with k steps
B)equivalence of two given Turing machines
C)language accepted by a given DFSA is nonempty
D)language generated by a CFG is nonempty

Question

Quizplus · Accepted Answer

The equivalence of two given Turing machines is undecidable because there is no algorithm that can determine for every pair of Turing machines whether they accept the same language. This is a consequence of the undecidability of the halting problem.

Which One of the Following Is Not Decidable