A Theory of the Learnable
Valiant defined it: a class of concepts is learnable if an algorithm exists that, in polynomial time and from a reasonable number of examples, returns a nearly correct answer with high probability.
Why it matters
Learning acquired a definition in which impossibility can be proved, and the question of how many examples are needed became mathematical.
The model is known as probably approximately correct learning. What matters is that the demand is weakened twice: the answer need only be approximate, and only probably so. Without those weakenings almost nothing is learnable. Computational learning theory, the link to Vapnik-Chervonenkis dimension and boosting all grew from it. Valiant received the Turing Award in 2010.