Véronique Terrier (GREYC, Université de Caen)

Les automates cellulaires sont un modèle de calcul massivement parallèle. Ce modèle de calcul tout en ayant une description simple et bien formalisée et capable de calcul universel.

En dimension 2, un automate cellulaire est constitué d’un tableau à 2 dimensions de composants élémentaires identiques appelés cellules. A une étape donnée, chaque cellule est dans un état donné. Au cours du temps l’état d’une cellule varie en fonction de son environnement local.

Ces changements d’états se font :

  • de manière synchrone : à chaque transition, les états de toutes les cellules sont modifiés en même temps;
  • de manière locale : chaque cellule change d’état en fonction des états de ses cellules voisines;
  • de manière uniforme : la fonction de transition est la même pour toutes les cellules.

Pour les automates cellulaires vus comme accepteurs de langages, on distingue une cellule du tableau pour récupérer le résultat. Un mot est alors accepté ou rejeté si au cours du calcul cette cellule distinguée entre dans un état d’acceptation ou de rejet.

Je m’intéresserai à la question du voisinage , c’est à dire l’environnement local de chaque cellule. En particulier, j’examinerai en quoi le choix du voisinage peut influer sur les capacités de calcul.