GATE CS 1990 Q3-vii — Undecidability

To determine which of the given problems are undecidable, we analyze each option:

1. An arbitrary Turing machine halts after $100$ steps:

   This is decidable. Since the number of steps is bounded by a constant ($100$), we can simply simulate the Turing machine for at most $100$ steps. If it halts within $100$ steps, we accept; otherwise, we reject. This simulation is guaranteed to terminate in finite time.

2. A Turing machine prints a specific letter:

   This is undecidable. We can reduce the Halting Problem to this problem. Given a Turing machine $M$ and input $x$, we can construct a new Turing machine $M'$ that simulates $M$ on $x$. If $M$ halts, $M'$ prints the specific letter. Thus, $M'$ prints the specific letter if and only if $M$ halts on $x$. Since the Halting Problem is undecidable, this problem is also undecidable.

3. A Turing machine computes the product of two numbers:

   This is undecidable. By Rice's Theorem, any non-trivial semantic property of the function computed by a Turing machine is undecidable. The property "computes the product of two numbers" is a semantic property of the function computed by the TM, and it is non-trivial (some TMs compute this function, while others do not). Therefore, it is undecidable.

Thus, options B and C are undecidable.