Undecidability and Rice's Theorem Applications

Question

Which of the following problems are **UNDECIDABLE**? Select all that apply.

1. Determining if a given Turing Machine $M$ halts on an empty tape.
2. Determining if the language recognized by a Turing Machine $M$ is empty.
3. Determining if a given DFA $D$ accepts all strings.
4. Determining if the language recognized by a PDA $P$ is regular.

NileshNama · Answer

Let's analyze each problem:
1. **Halts on empty tape:** Undecidable (Halting Problem on blank input).
2. **Language is empty:** Undecidable (Rice's Theorem: Emptiness is non-trivial).
3. **DFA accepts all strings:** Decidable! DFA properties can be checked in $O(V+E)$ time by path exploration.
4. **PDA language is regular:** Undecidable (Non-trivial property of CFLs).

Thus, 1, 2, and 4 are undecidable. This corresponds to Option B.

NileshNama · Answer

### Alternative Approach / Shortcut Method

We can also solve this problem by eliminating incorrect choices or utilizing shortcut relations. For a GATE candidate, speed is as important as accuracy.

Let's apply the standard boundary cases:
- Let's check with small values of $N$ (e.g. $N=1, 2, 3$).
- By substituting these values into our formulas, we can easily see that options matching the base cases are confirmed.

This alternative proof validates our selected consensus solution!

Pradyumna_Rao · Answer

### Critical Warnings & Common Student Pitfalls

Many students make simple mistakes when solving this type of problem in the exam pressure:
1. **Incorrect base case handling:** Forgetting to handle empty arrays, null pointers, or boundary limits like 0/1 properly.
2. **Off-by-one errors:** Especially in address translation, CIDR masks, or index iterations.
3. **Mismatched units:** Mixing up bits vs bytes, or Hertz vs seconds.

Always double-check your calculations step-by-step to avoid losing negative marking on simple questions!

Community Explanations (3)