Florent Becker (LIP, Lyon)

Dans la nature, le phénomène d’auto-assemblage est omni-présent: de « petites » entités interagissent, s’agrègent et forme des structures complexes, avec une forme et une fonction « intéressante ». Dans les années 90, une équipe de l’université de Standford, autour d’Erik Winfree, Ned Seeman et Leonard Adleman ont tenté d’utiliser des molécules d’ADN ayant la faculté de s’auto- assembler pour exécuter des algorithmes.

Je présenterai leur démarche, et le modèle théorique qui en découle, celui des pavages auto-assemblants, une variante des pavages de Wang. Ce modèle constitue un modèle de calcul original, que l’on pourrait comparer à des automates cellulaires en 1.5 dimensions. Je montrerai comment calculer avec ces objets, au niveau microscopique.

Malheureusement, le calcul avec ces objets tel qu’il était présenté traditionnellement se fait à très bas niveau, et il faut concevoir (et prouver !) des systèmes à partir des interactions microscopiques. Pour relever ce défi, je donnerai des pistes vers un langage de programmation adapté à l’auto- assemblage. Pour cela, nous verrons que la géométrie, qui est un peu oubliée dans l’approche classique, joue un rôle crucial.