|
Distinguished Lecturer Series
Sponsored by the Arthur and Rochelle Belfer
Institute of Mathematics and Computer Science
Professor Leslie Valiant
Harvard University
will speak on
When Biology is Computation
Abstract
We argue that computational models have an essential role in uncovering the
principles behind a variety of biological phenomena that cannot be
approached by other means. In this talk we shall focus on evolution.
Living organisms function according to complex mechanisms that operate in
different ways depending on conditions. Darwin's theory of evolution suggests
that such mechanisms evolved through random 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.
We start with the observation that Darwin's theory becomes a computational
theory once one is specific about how exactly the "random variation" and
the "selection" are done. The dilemma in being specific is that if one is
too restrictive about the basic mechanisms allowed then it becomes
implausible that all the complexity of biology can be expressed in terms
of them, while if one is too expressive then it is implausible that random
variation with selection can successively navigate this complex space as
changing conditions require.
In order to analyze this problem 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 current hypothesis 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. For example, we can
show that monotone Boolean conjunctions and disjunctions are demonstrably
evolvable over the uniform distribution, while Boolean parity functions are
demonstrably not. We suggest that the overall mechanism that underlies
biological evolution is "evolvable target pursuit", which consists of a
series of evolutionary stages, each one somewhat predictably pursuing an
evolvable target in the technical sense suggested above, each target being
rendered evolvable by the serendipitous combination of the environment and
the outcomes of previous evolutionary stages.
The lecture will take place
in the Lecture Hall, Room 1, Ziskind Building
on Sunday, November 9, 2008
at 11:00
| 
