UGA

L3 Informatique

Modèles de Calcul - Machines de Turing

Projet Automates Cellulaires


Modalités d'évaluation du projet


Automates Cellulaires

Le modèle de calcul des automates cellulaires est un modèle simple et massivement parallèle de calcul. L'idée est de considérer l'évolution des états d'un ensemble de cellules en contact les unes avec les autres. Toutes les cellules sont codées par un même automate d'états finis. A chaque top d'horloge toutes les cellules changent d'état en fonction de leur état et de celui de leurs voisines : la transition est codée dans l'automate donnant l'évolution des états.

Un exemple est un automate à une dimension dont les états sont soit "0" soit "1" (ou blanc/noir). Sur une ligne de cellule chaque cellule a deux cellules voisines. Ainsi pour définir un automate il faut dire pour chacune des 8 configurations possibles (les deux cellules plus l'état de la cellule centrale) si le nouvel état de la cellule est 0 ou 1. Prenons l'automate suivant:

  1. 0,0,0 => 1
  2. 0,0,1 => 1
  3. 0,1,0 => 0
  4. 0,1,1 => 0
  5. 1,0,0 => 1
  6. 1,0,1 => 0
  7. 1,1,0 => 1
  8. 1,1,1 => 1

Alors la ligne suivante (en imaginant que les cellules sur le bord sont à côté de cellules qui sont à "0"):

1 1 1 0 0 0 1 1 1 0 1 0

va évoluer en un pas calcul en la ligne suivante:

0 1 1 1 1 1 0 1 1 0 0 1
Pour calculer la transformation de la première cellule on utilise la règle (4) (car on suppose que l'état de la cellule à gauche de la première cellule est toujours 0) c'est-a_dire que 0,1,1 => 0. Pour la seconde cellule il s'agit d'utiliser la règle (8) 1,1,1 => 1 etc.

Implantation d'un simulateur d'automates cellulaires 2D : le jeu de la vie

Description provenant de wikipedia:

Le « jeu de la vie » est un automate cellulaire bidimensionnel où chaque cellule peut prendre deux valeurs (« 0 » ou « 1 », mais on parle plutôt de « vivante » ou « morte ») et où son état futur est déterminé par son état actuel et par le nombre de cellules vivantes parmi les huit qui l'entourent :

En apparence simples, ces règles font émerger une forte complexité. Un exemple d'évolution est le suivant (en interprétant les cases noires par 1 et les blanches par 0).

Universalité en relation aux machines de Turing

Les automates cellulaires permettent de calculer toutes les fonctions calculables. Pour cela un automae cellulaire à une dimension suffit. On peut montrer cela formellement en simulant une machine de Turing par un automate cellulaire de dimension 1. On peut voir la bande de la machine de Turing comme une ligne de cellules.

Universalité intrinsèque

Une autre manière d'approcher l'universalité de ce modèle de calcul est de considérer l'universalité à l'intérieur même du modèle de calcul. Un automate cellulaire intrinsèquement universel est un automate capable de simuler pas à pas le comportement de n'importe quel automate cellulaire de même dimension. Plus précisément, l'idée de simulation pas à pas repose sur les principes suivants :

Ainsi, par exemple, le jeu de la vie est capable de simuler pas à pas l'automate D à 2 états (noir et rouge) qui effectue un simple décalage des états vers le sud-est :

Ainsi, pour simuler le comportement de B à partir d'une certaine configuration initiale, il suffit de fabriquer une configuration du jeu de la vie où chaque groupe est soit rempli de cellules mortes, soit d'un planeur selon l'état de la cellule qui lui correspond dans B.