Seminar on Algorithms Everywhere by Dr. Pierre-Etienne Meunier, Caltech

I will try to show, with two examples of systems I have worked with, how the language of computation can be used to describe and understand complexity in "natural" systems, or at least models thereof. Beginning with the example of elementary cellular automata, I will show, using extremely basic computational arguments, that most of them have simple dynamics, which had been an open question for decades. Then, my next example will be algorithmic self-assembly. This model has been developed to construct nano-things out of DNA, which are currently the object of a large number of experiments. Again, a simple argument about the amount of information "flowing through the system" will help us to prove that cooperation between tiles is needed to do interesting things. The computational abilities of the particular model I will talk about have been conjectured weak more than ten years ago, in the first publication on self-assembly. Moreover, our last result is of particular importance for experiments with DNA, since the fine control of cooperation between tiles is still not well mastered for non-trivial shapes or computations.   

Momoko Zamami 

Biological Physics Theory Unit

Okinawa Institute of Science and Technology Graduate University

1919-1 Tancha, Onna-son, Okinawa 904-0495 JAPAN

Tel: +81-98-966-2116 (Direct) +81-98-966-8711 (Main)

http: //www.oist.jp