18 février 2013

Pierre-Etienne Meunier (LAMA - Université de Savoie) salle des thèses

Je parlerai d’une méthode générique pour fabriquer des conditions nécessaires d’intrinsèque universalité pour les automates cellulaires. Cette notion d’universalité est plus forte que l’universalité Turing, et préserve une grande quantité d’invariants topologiques. L’idée de mon travail est de définir un problème de décision sur la dynamique d’un automate cellulaire, puis de prouver que la complexité de communication de ce problème est croissante avec une notion de simulation. Enfin, de montrer l’existence d’un automate cellulaire de complexité de communication Ω(n). La construction d’un protocole de communication simple résolvant le problème pour un automate cellulaire F montre alors que F n’est pas intrinsèquement universel.