I. GIVEN A TURING MACHINE $M$, DOES $M$ HALT ON ALL INPUTS?
- UNDECIDABLE. This is the "Total" problem. It's a non-trivial property of the TM's behavior (not language, so Rice's Theorem doesn't directly apply, but it's famously undecidable and not R.E.).
II. GIVEN A CONTEXT-FREE GRAMMAR $G$, IS THE LANGUAGE $L(G)$ FINITE?
- DECIDABLE. We can build a graph of dependencies between non-terminals. If there is a reachable and productive non-terminal that is part of a cycle (e.g., $A \Rightarrow^* w_1 A w_2$ ), the language is infinite. This is a finite, checkable graph problem.
III. GIVEN A TURING MACHINE $M$, DOES $L(M)$ CONTAIN AT LEAST 5 STRINGS?
- UNDECIDABLE. This is a non-trivial property of the language $L(M)$ (some R.E. languages are empty, some have $\geq 5$ strings). By Rice's Theorem, this is undecidable.
IV. GIVEN TWO DFAS $A$ AND $B$, IS $L(A) \subseteq L(B)$ ?
- DECIDABLE. This is equivalent to asking if $L(A) \cap \overline{L(B)}-0$.
- Regular languages are closed under complement (so $\overline{L(B)}$ is regular) and intersection (so $L(A) \cap \overline{L(B)}$ is regular).
- The emptiness problem for regular languages is decidable.
THE DECIDABLE PROBLEMS ARE II AND IV.
