“A Theory of the Learnable,” by Leslie G. Valiant, was published in Communications of the ACM in 1984 (volume 27, pages 1134 to 1142). It is one of the founding documents of computational learning theory and introduced the framework now known as Probably Approximately Correct, or PAC, learning. The work was part of the body of research for which Valiant later won the Turing Award.
Before this paper, “learning” was studied informally. Valiant asked a sharp, computer-science question: which classes of concepts can be learned from examples, efficiently, with provable guarantees? His answer set out a precise contract. A learner sees a number of randomly drawn, labeled examples and must output a hypothesis that, with high probability (the “probably”), has small error (the “approximately correct”). A concept class is PAC-learnable if some algorithm can meet this contract using a number of examples and an amount of computation that grow only polynomially as the desired confidence and accuracy tighten.
This reframing made it possible to prove that certain families of concepts are learnable and to reason about the sample size and running time learning requires. It connected closely to the contemporaneous theory of VC dimension, which measures the capacity of a hypothesis class, and together they gave the field its mathematical backbone.
For a general reader, PAC learning matters because it turned a vague aspiration, that machines can learn from data, into a rigorous theory with definitions, theorems, and limits, much as earlier theory had done for computation itself.