{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T21:45:31Z","timestamp":1780436731968,"version":"3.54.1"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["NSF-CCR-0310882NSF-CCF-0432037NSF-CCF-04-27129"],"award-info":[{"award-number":["NSF-CCR-0310882NSF-CCF-0432037NSF-CCF-04-27129"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["NSF-CCR-0310882NSF-CCF-0432037NSF-CCF-04-27129"],"award-info":[{"award-number":["NSF-CCR-0310882NSF-CCF-0432037NSF-CCF-04-27129"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2009,1]]},"abstract":"<jats:p>Living organisms function in accordance with complex mechanisms that operate in different ways depending on conditions. Darwin's theory of evolution suggests that such mechanisms evolved through variation guided by natural selection. However, there has existed no theory that would explain quantitatively which mechanisms can so evolve in realistic population sizes within realistic time periods, and which are too complex. In this article, we suggest such a theory. We treat Darwinian evolution as a form of computational learning from examples in which the course of learning is influenced only by the aggregate fitness of the hypotheses on the examples, and not otherwise by specific examples. We formulate a notion of evolvability that distinguishes function classes that are evolvable with polynomially bounded resources from those that are not. We show that in a single stage of evolution monotone Boolean conjunctions and disjunctions are evolvable over the uniform distribution, while Boolean parity functions are not. We suggest that the mechanism that underlies biological evolution overall is \u201cevolvable target pursuit\u201d, which consists of a series of evolutionary stages, each one inexorably pursuing an evolvable target in the technical sense suggested above, each such target being rendered evolvable by the serendipitous combination of the environment and the outcomes of previous evolutionary stages.<\/jats:p>","DOI":"10.1145\/1462153.1462156","type":"journal-article","created":{"date-parts":[[2009,2,4]],"date-time":"2009-02-04T13:01:58Z","timestamp":1233752518000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":61,"title":["Evolvability"],"prefix":"10.1145","volume":"56","author":[{"given":"Leslie G.","family":"Valiant","sequence":"first","affiliation":[{"name":"Harvard University, Cambridge, Massachusetts"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2009,2,3]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"B\u00e4ck T. Fogel D. B. and Michalewisz Z. (Eds.). 1997. Handbook of Evolutionary Computation. Oxford Univ. Press Oxford UK.  B\u00e4ck T. Fogel D. B. and Michalewisz Z. (Eds.). 1997. Handbook of Evolutionary Computation. Oxford Univ. Press Oxford UK."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.1098119"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/76359.76371"},{"key":"e_1_2_1_4_1","unstructured":"B\u00fcrger R. 2000. The Mathematical Theory of Selection Recombination and Mutation. Wiley Chichester UK.  B\u00fcrger R. 2000. The Mathematical Theory of Selection Recombination and Mutation. Wiley Chichester UK."},{"key":"e_1_2_1_5_1","unstructured":"Darwin C. 1859. On the Origin of Species by Means of Natural Selection. John Murray London UK.  Darwin C. 1859. On the Origin of Species by Means of Natural Selection. John Murray London UK."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1038\/nrg1527"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","first-page":"1667","DOI":"10.1093\/genetics\/148.4.1667","article-title":"Rates of spontaneous mutation","volume":"148","author":"Drake J. W.","year":"1998","journal-title":"Genetics"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90002-3"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374465"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221014"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Fisher R. A. 1930. The Genetical Theory of Natural Selection. Oxford Univ. Press Oxford UK.  Fisher R. A. 1930. The Genetical Theory of Natural Selection. Oxford Univ. Press Oxford UK.","DOI":"10.5962\/bhl.title.27468"},{"key":"e_1_2_1_12_1","unstructured":"Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman San Francisco CA.   Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman San Francisco CA."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221019"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293351"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/174644.174647"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Kearns M. and Vazirani U. 1994. An Introduction to Computational Learning Theory. MIT Press Cambridge MA.   Kearns M. and Vazirani U. 1994. An Introduction to Computational Learning Theory. MIT Press Cambridge MA.","DOI":"10.7551\/mitpress\/3897.001.0001"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1038\/217624a0"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.022629899"},{"key":"e_1_2_1_20_1","unstructured":"Maynard-Smith J. 1982. Evolution and the Theory of Games. Cambridge Univ. Press Cambridge UK.  Maynard-Smith J. 1982. Evolution and the Theory of Games. Cambridge Univ. Press Cambridge UK."},{"key":"e_1_2_1_21_1","unstructured":"Papadimitriou C. H. 1994. Computational Complexity. Addison-Wesley Reading MA.  Papadimitriou C. H. 1994. Computational Complexity. Addison-Wesley Reading MA."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/48014.63140"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Roff D. A. 1997. Evolutionary Quantitative Genetics. Chapman & Hall New York.  Roff D. A. 1997. Evolutionary Quantitative Genetics. Chapman & Hall New York.","DOI":"10.1007\/978-1-4615-4080-9"},{"key":"e_1_2_1_24_1","volume-title":"Foundations of Genetic Algorithms","author":"Ros J. P."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(00)00002-3"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/1597348.1597438"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1558-5646.1996.tb02339.x"},{"key":"e_1_2_1_29_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 28th International Colloquium on Automata, Languages and Programming","author":"Wegener I."},{"key":"e_1_2_1_30_1","unstructured":"Wright S. 1968--1978. Evolution and the Genetics of Populations A Treatise. University of Chicago Press Chicago IL.  Wright S. 1968--1978. Evolution and the Genetics of Populations A Treatise. University of Chicago Press Chicago IL."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1462153.1462156","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1462153.1462156","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:30:14Z","timestamp":1750253414000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1462153.1462156"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,1]]}},"alternative-id":["10.1145\/1462153.1462156"],"URL":"https:\/\/doi.org\/10.1145\/1462153.1462156","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1]]},"assertion":[{"value":"2006-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-02-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}