GATE CS 1997 Q6.5 — Undecidability

To determine which of the given problems is not decidable, let us analyze each option:

1. Given a Turing machine $M$, a string $s$, and an integer $k$, $M$ accepts $s$ within $k$ steps:
   Decidable. We can construct a universal Turing machine to simulate $M$ on input $s$ for exactly $k$ steps. Since the number of steps $k$ is finite, the simulation is guaranteed to halt. If $M$ reaches an accepting state in $\le k$ steps, we accept; otherwise, we reject.
2. Equivalence of two given Turing machines:
   Undecidable. Testing whether two arbitrary Turing machines $M_1$ and $M_2$ accept the same language ($L(M_1) = L(M_2)$) is a well-known undecidable problem. This can be proven via reduction from the Halting Problem or by applying Rice's Theorem (as equivalence is a non-trivial semantic property of Turing machines).
3. Language accepted by a given finite state machine is not empty:
   Decidable. The emptiness problem for Finite Automata (FA) is decidable. We can use graph reachability algorithms (like BFS or DFS) to check if there is a path from the start state to any accepting state.
4. Language generated by a context-free grammar is non-empty:
   Decidable. The emptiness problem for Context-Free Grammars (CFGs) is decidable. We can determine if $L(G) \neq \emptyset$ by identifying the set of "generating" variables (variables that can eventually derive a string of terminals) and checking if the start symbol $S$ is generating.

Therefore, the problem in option B is not decidable.