UGA
L3 Informatique
Modèles de Calcul - Machines de Turing
Projet Automates Cellulaires
Modalités d'évaluation du projet
- Dates : le projet est à rendre pour le 7/4/2021.
- Le projet se fera en binôme.
- Retour : les retours se feront par mail à
frederic.prost@univ-grenoble-alpes.fr avec comme sujet [MCAL] projet
étudiant.
- Un compte-rendu concis, complet et précis, au format pdf, nomée "nom1-nom2.pdf
dans lequel vous donnerez vos réponses aux questions.
- Les fichiers d'implantation concernant les réponses des questions 1, 2 . Vous pouvez utiliser le langage de programmation
de votre choix. Vous devez indiquer dans le compte-rendu comment il faut compiler et éxécuter vos programmes.
- Une soutenance d'une dizaine de minutes est prévue pour chaque binôme.
- Planning des soutenances
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:
- 0,0,0 => 1
- 0,0,1 => 1
- 0,1,0 => 0
- 0,1,1 => 0
- 1,0,0 => 1
- 1,0,1 => 0
- 1,1,0 => 1
- 1,1,1 => 1
Alors la ligne suivante (en imaginant que les cellules sur le bord sont à côté de cellules qui sont à "0"):
va évoluer en un pas calcul en la ligne suivante:
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.
-
- Question 1 -
Donner un automate cellulaire à une dimension qui reconnait les mots anb n. On simulera le fonctionnement de l'automate par une bande sur laquelle l'état inital des cellules sera le mot à reconnaitre avec deux cellules sur les côtés qui délimitent les bords, on prendra l'état 0 pour coder cela. Par exemple pour le mot aabbbaa on considère le morceau de bande initialisé dans les états suivants :
Le calcul sera considéré comme terminé si toutes les cellules passent dans soit dans l'état y, qui indique que le mot a été reconnu, soit dans l'état N qui indique que le mot n'a pas été reconnu. Les règles d'évolution pour ces états seront Y,Y,Y => Y et N,N,N => N. pour les bords on a les règles x,0,y => 0 avec x et y n'importe quel état de l'automate (autrement dit les bords ne bougent pas). Comme le mot aabbbaa n'est pas de la forme anb n
le calcul sur l'automate représenté juste avant doit terminer en :
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 :
- Si la cellule est vivante et entourée par deux ou trois cellules vivantes, elle reste en vie à la génération suivante,
sinon elle meurt.
- Si la cellule est morte et entourée par exactement trois cellules vivantes, elle naît à la génération suivante.
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).
-
- Question 2 -
Implanter un simulateur d'automates cellulaires en 2 dimension sur une grille n par m.
C'est à dire un programme qui prend en entrée une fichier décrivant les règles d'évolution de l'automate cellulaire, une description
initiale de la grille et un nombre de pas d'évolution. On prendra soin de préciser les conditions sur les bords. Votre programme devra
permettre de visualiser l'évolution de l'état des automates.
-
- Question 3 -
Donnez le programme qui implante le jeu de la vie dans le formalisme de votre programme.
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.
-
- Question 4 -
Donnez précisément la manière de simuler une machine de Turing (définie par son programme, c'est-à-dire
l'ensemble des quadruplets de la MT) par un automate cellulaire à 1 dimension travaillant sur une ligne infinie. On prendra soin
de bien spécfier l'état initial de la bande dans le modèle des automates cellulaires en fonction de l'état initial dans les
machines de Turing. Le modèle des machines de Turing à simuler sera celui vu en cours (avec des quadruplets).
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 :
- dans l'automate simulateur, on forme des groupes de cellules voisines, tous identiques, qui recouvrent régulièrement le réseau de cellules ; chaque groupe dans le simulateur représente une cellule simple de l'automate simulé ;
- à chaque état de l'automate simulé correspond une configuration d'états de groupe dans l'automate simulateur ;
- l'automate simulateur peut utiliser plusieurs étapes pour simuler une étape de l'automate simulé.
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 :
- les groupes de cellules dans le jeu de la vie sont des carrés de {\displaystyle 4\times 4}4\times 4 cellules ;
- l'état noir de B correspond à un groupe de cellules toutes mortes et l'état rouge correspond à un planeur entouré de cellules mortes et ajusté dans une certaine position au sein du groupe ;
- une étape de B est simulée toutes les 16 étapes du jeu de la vie.
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.
-
- Question 5 -
On considère l'automate cellulaire E à 2 états, disons 0 et 1, qui décale les états vers l'est. Donnez une manière de simuler l'automate E dans le jeu de la vie. Indiquez clairement à quelle configuration correspondent les états 0 et 1 et combien de pas de calcul il faut pour simuler l'évolution d'un pas de l'automate E.