Alex Borello (LIF, Marseille)

Les automates cellulaires constituent un modèle de calcul massivement parallèle qui, à l’instar de celui des machines de Turing, qu’il peut simuler, peut être vu dans le cadre de la reconnaissance de langages. Il est en général difficile d’établir des bornes inférieures sur la puissance de calcul de tels modèles ; ainsi, on connaît peu de techniques permettant d’obtenir des résultats négatifs. On donne ici quelques pistes et exemples en dimension 1 et en temps réel, qui est la plus petite complexité temporelle raisonnable pour ce modèle (au sens où le mot en entrée doit pouvoir être lu entièrement par l’automate considéré).