Living cells function according to complex mechanisms that operate in different ways depending on conditions. Evolutionary theory suggests that such mechanisms evolved as a result of a random search guided by selection and realized by genetic mutations. However, as some observers have noted, there has existed no theory that would explain quantitatively which mechanisms can so evolve, and which are too complex. In this paper we provide such a theory. As a starting point, we relate evolution to the thory of computational learning, which addresses the question of the complexity of recognition mechanisms that can be derived from examples. We derive a quantitative notion of evolvability. The notion quantifies the limited sizes of populations and the limited numbers of generations that need to be sufficient for the evolution of significant classes of mechanisms. It is shown that in any one phase of evolution where selection is for one beneficial behavior, certain specific classes of mechanisms are demonstrably evolvable, while certain others are demonstrably not.