[CoA 2014] Damien Woods (B/B)

troisièmes journées du GT CoA Complexité et Algorithmes :
Algorithmes naturels
du mercredi 10 septembre 12h30 au vendredi 12 septembre 13h30, Université Paris Diderot
LIAFA, Salle 1009, Bâtiment Sophie Germain Paris 13ème

13:45-14:45 - Exposé invité n°1 : Damien WOODS (Caltech, professeur invité au LIAFA)
Intrinsic universality and the computational power of self-assembly [B/B]

Our story is set in the world of algorithmic self-assembly, where small unit-sized tiles stick together to form large complicated structures. This kind of self-assembly is best described as an asynchronous and distributed computational process. We regale the forging of a powerful tool, simulation. We tell of its wielding by brave adventurers to classify and separate the computational and expressive power of self-assembly models.
Our journey begins with the result that there is a single intrinsically universal tile set, that with proper initialization and scaling, simulates any tile assembly system. This intrinsically universal tile set exhibits something stronger than Turing universality: it directly simulates the geometry and dynamics of any simulated system. From there we find that there is no such tile set in the noncooperative, or temperature 1, model, proving it weaker than the full tile assembly model. In the two-handed or hierarchical model, where large assemblies can bind together in one step, we encounter an infinite set, of infinite hierarchies, with strictly increasing simulation power. Towards the end of our adventure, we find one tile to rule them all: a single rotatable, flipable, polygonal tile that can simulate any tile assembly system. It seems this could be the beginning of a much longer journey, so directions for future work are suggested.