Exercises
The power of informant over text. Gold showed that the class \(\mathcal{L}\) of all recursive languages is \(\mathbf{Ex}\)-identifiable from informant (both positive and negative examples) but not from text (positive examples only).
Prove the informant direction: construct an \(\mathbf{Ex}\)-learner \(M\) that identifies any recursive language \(L\) from informant. Hint: Dovetail over all programs \(\varphi _0, \varphi _1, \ldots \), and at time \(t\) hypothesize the smallest index \(e\) consistent with all labeled data seen so far. Use the fact that the informant eventually presents every string with its correct label, so incorrect indices are eventually refuted.
Explain precisely why this learner fails from text. Identify the step in the argument that relies on negative examples, and show that no text-based substitute exists. (Hint: The learner can refute “\(\varphi _e\) includes \(x\)” from an informant presentation of \((x, 0)\), but a text for \(L\) never explicitly says “\(x \notin L\)”, it merely fails to present \(x\), which is indistinguishable from delay.)
\(\mathbf{Ex}\)-identification of co-finite languages. Let \(\mathcal{L}_{\mathrm{cof}}\) be the class of all co-finite languages over \(\mathbb {N}\): \(L \in \mathcal{L}_{\mathrm{cof}}\) iff \(\mathbb {N}\setminus L\) is finite.
Prove that \(\mathcal{L}_{\mathrm{cof}}\) is \(\mathbf{Ex}\)-identifiable from text. (Hint: Every co-finite language \(L\) contains all but finitely many natural numbers. A text for \(L\) eventually presents every element of \(L\), so after time \(n_0\), every natural number \(\leq n_0\) has either appeared in the text (and is in \(L\)) or has not appeared (and may or may not be in \(L\)). Design a learner that waits long enough to conclude that unseen small numbers are not in \(L\).)
Prove that \(\mathcal{L}_{\mathrm{fin}} \cup \mathcal{L}_{\mathrm{cof}}\) (all finite and all co-finite languages together) is not \(\mathbf{Ex}\)-identifiable from text. (Hint: Apply Gold’s impossibility theorem. Verify that this class contains all finite languages and at least one infinite language.)
The result of (b) is sharper than Gold’s theorem applied to “all finite + one infinite”: the single infinite language is itself very structured (co-finite). Explain why the structure of the infinite language does not help, what makes the diagonalization work is not the complexity of \(L_\infty \) but the learner’s inability to distinguish “finite set, done growing” from “co-finite set, still growing.”