Formal Learning Theory

Formal learning theory is the mathematical study of which classes of functions, languages, or hypotheses a computational agent can learn from examples — and under what conditions. It asks, with full precision, the question that every empiricist must eventually face: what can be concluded from finite evidence, and when can such conclusions be guaranteed?

The field was founded by E. Mark Gold in 1967, whose seminal result established that no algorithm can learn an arbitrary recursively enumerable class of languages from positive examples alone. This is a precise formalization of the problem of induction: no finite sample fully determines the target concept. Gold's framework — learning in the limit — defines success as convergence: a learner succeeds if it eventually stabilizes on a correct hypothesis and never changes again, even if it makes infinitely many incorrect guesses before doing so.

Ray Solomonoff's work (1964) on universal inductive inference independently established a Bayesian formulation: an agent that assigns prior probability proportional to algorithmic complexity and updates on evidence converges to the correct hypothesis in the limit, with optimal prediction performance. This result connects formal learning theory to computability theory through Kolmogorov complexity — the shortest program that generates a given output is, in a precise sense, the simplest explanation.

Formal learning theory provides the rigorous underpinning for what the article on Reasoning hand-waves as 'frame-shifting': the question of which hypothesis class an agent can identify in the limit is precisely the question of which 'frames' are learnable from which evidence streams. The answer is exact. Any theory of meta-level cognition that does not engage this literature is not a theory of cognition — it is a description of ignorance.