The Turing Lecture

August 14th, 2011 by Erwin Gianchandani Leave a reply »

Leslie Valiant receives the 2010 A.M. Turing Award. From left to right: John White, ACM CEO; Shekar Borkar, Intel Fellow; Alfred Spector, Google VP Research and Special Initiatives; Turing Award winner Leslie Valiant, Harvard University; and Alain Chesnais, ACM President [image courtesy ACM.org].Leslie Valiant, the winner of the 2010 A.M. Turing Award for his “transformative contributions to the theory of computation,” delivered the Turing Lecture at the 2011 Federated Computing Research Conference, held in San Jose, CA, in early June.

Valiant’s lecture — titled “The Extent and the Limitations of Mechanistic Explanations of Nature” — is now online (after the jump):

Have thoughts about Valiant’s lecture? Share your comments below!

(Contributed by Erwin Gianchandani, CCC Director)

  • http://www.facebook.com/ron.maimon.7 Ron Maimon

    The Turing lecture presents a very important idea: that it is impossible to build a convincing sophisticated computational circuit using point mutations in any reasonable time scale. This point was made intuitively by Pauli in the 1950s, when it was a response to modern synthesis evolution. It has been made by nonscientists as well, who find it hard to buy the idea of evolution happening by random point mutation.

    The idea that there is a learning mechanism for modifying the genome is obviously true, and it is fantastic that someone with some clout has finally taken this position. But the learning hypothesis is not very persuasive because it is missing the main point. The memory capacity of the proteins is just too small to account for the computational complexity of the DNA rewriting, the number of protein combinations is generally vastly smaller than the number of DNA combinations. This paradox was very clear to those who studied protein networks, it makes it difficult to imagine any model of evolution which operates on DNA using proteins alone. To modify gigabytes of functional data, You need a molecule which can encode gigabytes of random-access data in a read/write way, in a dense encoding. The only real candidate, excluding DNA methylation and DNA conformation (which are recently emphasized hacks with similar function) is RNA.

    The lack of direct communication or compatibility between the protein and DNA level information demands that the information about future mutations must be stored in self-modifying computing strands of RNA. This is a firm prediction, it must be so, and yet it is not accepted fully within biology.

    This prediction allows one to predict that the DNA in the cell is mostly noncoding, since the coding region is controlled and evolved by the noncoding parts. It requires that the noncoding part is transcribed into RNA despite being noncoding. This is also now known to be true. It provides the only convincing role for the massive amount of long noncoding RNA in the nucleus. This RNA is computing, making a nervous system for the cell, and this computation provides the only plausible mechanism for machine-learning in the genome.

    The computation in RNA requires that the RNA can distinguish different strands from one another, and this is done through complementary binding, and splicing/resplicing events in RNA. The hypothesis is that these events are making closed-loop computation with each other, without any need for translation to proteins, using only proteins available in the nucleus.

    The RNA/RNA events and RNA reverse transcription (which is required for the evolution to be influenced by the RNA) are the “strange events” which are described in the video, but they are not all that random, they are constrained by the allowed mutagenesis in the RNA computing system in the nucleus.

    The communication between RNA and DNA predicts that there are reverse transcriptase genes in the genome (this is also true, in ERVs), and that these are transcribed and active in certain cases. This has been observed in human tissue in cancer cells, where full functional HERVs are produced, including the polymerase, which allows for reverse transcription. The reverse transcription functionality of the human genome is important, since it allows you to couple the RNA computation back into the DNA.

    The contains complementary matching motifs which allow self binding (true and surprising) and that that it is composed of interpretable domains with features which are not random.

    The “evolvability” condition then presented here is much too strict, the evolution can include rewriting of the code which is sensible, directed by the RNA networks in an egg.

    This completely resolves the paradox of evolution presented in the video, but it introduces vastly more computation into the cell than is known at present. It demands that the RNA computation is sufficiently complex to essentially have a model of the protein production and the noncoding RNA production in the cell, so that it can sensibly modify the DNA for future generations.

    These predictions are biologically surprising, and they are the only plausible way to allow for evolution to produce observed biological complexity, yet are not accepted fully,