Alan Turing Celebration Lecture: Leslie Valiant

This year marks the 100th anniversary of the birth of the "father of computer science," Alan Turing. His legacy is recognized with the Turing Award, the "Nobel prize" of computer science. The Department of Computer Science is honoured to host 2010 Turing award winner Leslie Valiant, who has made fundamental contributions to our understanding of computation, communication and learning.

Abstract:
This year marks the 100th anniversary of the birth of the "father of computer science," Allan Turing. His legacy is recognized with the Turing Award, the "Nobel prize" of computer science. The Department of Computer Science is honoured to host 2010 Turing award winner Leslie Valiant, who has made fundamental contributions to our understanding of computation, communication and learning.

Living organisms function according to protein circuits. Darwin’s theory of evolution suggests that these circuits have evolved through variation guided by natural selection. However, the question of which circuits can so evolve in realistic population sizes and within realistic numbers of generations has remained essentially unaddressed.

We suggest that computational learning theory offers the framework for investigating this question, of how circuits can come into being adaptively from experience, without a designer. We formulate evolution as a form of learning from examples. The targets of the learning process are the functions of highest fitness. The examples are the experiences. The learning process is constrained so that the feedback from the experiences is Darwinian. We formulate a notion of evolvability that distinguishes function classes that are evolvable with polynomially bounded resources from those that are not.  

The dilemma is that if the function class, say for the expression  levels of proteins in terms of each other, is too restrictive, then it  will not support biology, while if it is too expressive then no  evolution algorithm will exist to navigate it. We shall review current work in this area.