Formal Learning Theory Kernel: Blueprint v1

5.7 What This Chapter Established

This chapter introduced Gold-style identification in the limit, the oldest paradigm in formal learning theory, and established five structural facts:

  1. Gold’s impossibility theorem (Theorem 5.4): any class containing all finite languages and at least one infinite language is not \(\mathbf{Ex}\)-identifiable from text. The proof is by diagonalization, the first impossibility result in learning theory, and one whose proof technique (adversarial stream construction) has no analogue in PAC or online theory.

  2. The identification hierarchy (Section 5.3): the chain \(\mathbf{FIN}\subsetneq \mathbf{Ex}\subsetneq \mathbf{BC}\) is strict, with the Case–Smith separation (Theorem 5.8) providing the witness for \(\mathbf{BC}{\gt} \mathbf{Ex}\). The hierarchy is not a sequence of definitions but a chain of theorems.

  3. Relaxations form a lattice (Section 5.4): anomalous, monotonic, and vacillatory learning branch off from \(\mathbf{Ex}\), each modifying a different aspect of the convergence requirement. Trial-and-error learning connects to \(\Delta ^0_2\) in the arithmetical hierarchy.

  4. Mind-change complexity is ordinal-valued (Section 5.5): the Freivalds–Smith characterization shows that the right complexity measure for \(\mathbf{Ex}\)-identification uses transfinite ordinals, not integers. The full treatment is in the textbook’s Chapter 13 (Mind-Change Ordinals).

  5. The three paradigms are pairwise incomparable (Section 5.6): PAC, online, and Gold-style identification are separated in every direction by explicit witnesses. This is the most important structural fact about the landscape of learning theory.

The recursion-theoretic character of this chapter, diagonalization proofs, connections to the arithmetical hierarchy, ordinal-valued measures, contrasts sharply with the probabilistic character of Chapter 3 and the combinatorial character of Chapter 4. Each paradigm brings its own mathematical world. The separations of Section 5.6 are consequences of this fact: the paradigms use different proof techniques because they formalize genuinely different questions.