Exercice java machine de Turing : algorithme et POO de base

Le but est d'écrire un programme Turing.java permettant de simuler une machine de Turing.

Proposition de méthode :

1. Définissez un certain nombre de constantes utiles accessibles par toutes vos classes:

   char EPSILON='e'; int POSITION_INITIALE=0; int UNDEF=0; int ETAT_INITIAL=1;

2. Pour simuler une bande de longueur infinie, vous pouvez utiliser une String :
   • lorsque l'on cherchera à déplacer la tête au-delà du dernier élément, il suffira de créer un élément supplémentaire, initialisé avec le symbole epsilon (représenté par le caractère 'e').
   • lorsque l'on cherchera à déplacer la tête avant le premier élément, il suffira d'insérer en début de chaine le symbole epsilon
3. La tête de lecture sera représentée simplement par une classe d'objets ayant pour attribut un entier , indiquant sa position courante. A cette classe d'objet seront associées les méthodes permettant d'avancer et de reculer la tête de lecture (i.e. incrémenter/décrémenter sa position).

1. Pour représenter la table de transitions, vous utiliserez un tableau à deux dimensions. Ce tableau aura trois colonnes (une par valeur possible du caractère courant ([ 0, 1, epsilon]));
   
   
   • chaque 'case' définissant une transition est un objet de type Transition

   class Transition { private int etat; private char caractere; private int deplacement; }

2. Écrivez une classe TMachine, simulant une machine de Turing.

   Vous aurez besoin des attributs suivants :

   • un entier (ou un type prédéfini par vous) modélisant l'état actuel de la machine
   • une bande
   • une tête de lecture
   • une table de transitions
3. Définissez les méthodes suivantes :
   • un constructeur permettant de créer une machine de Turing
     TMachine(final Transition[][] table). Ce constructeur devra également mettre l'état actuel à ETAT_INITIAL, la bande à la chaine vide et la tête de lecture à POSITION_INITIALE
   • une méthode permettant de ré-initialiser la machine (pour recommencer avec une nouvelle entrée)
     void reinitialise(final String entree). L'état actuel sera remis à ETAT_INITIAL, la bande initialisée au moyen de entree et la tête de lecture sera remise à POSITION_INITIALE
   • les méthodes implémentant les primitives de lecture et d'écriture de la bande  :
     char lecture(); lit le caractère 'courant' de la bande
     void ecriture(char c); remplace dans la bande le caractère courant par la valeur transmise en argument
     

     Notez que, dans l'implémentation proposée, lecture et ecriture peuvent changer la valeur de tete : on simulera ainsi le fait que la bande est infinie, en insérant le bon nombre d'epsilons en début de bande lorsque la position de la tête est négative (naturellement, lorsque les espilons auront étés insérés, on devra repositionner la tête à zéro). [on aurait également pu choisir d'effectuer ces opérations - simuler une bande infinie - lors des déplacements de la tête...]

   • une méthode permettant de démarrer la simulation de la machine.
     Choisissez une convention sur la valeur de l'état pour stopper la machine (par exemple, une valeur négative).
   • une méthode permettant d'afficher l'etat de la machine de Turing selon l'exemple d'exécution donné ci-dessous.

Application 1: Test de Parité

Testez votre machine avec l'exemple du cours testant la parité de l'entrée.

Avec la modélisation proposée, utilisez la syntaxe suivante pour définir une table de transition (utilisée par le constructeur de TMachine):

La constante UNDEF représente un état non défini également utilisé pour "l'ordre de fin d'exécution".

Dans cet exemple, on suppose que le déplacement vers l'avant est représenté par la valeur +1, et le déplacement vers l'arrière par -1.

Exemple (détaillé) d'exécution :

Application 2: Inversion de séquence sur une Machine de Turing

Écrivez (sur papier) la table de transition d'une machine de Turing réalisant l'inversion d'une séquence de bits.

Par exemple, si l'on a 1101 en entrée, on devra avoir 1011 en sortie.

On supposera que:

• la bande de longueur infinie ne contient rien d'autre que la séquence, ce qui signifie qu'à l'exception de la séquence, tous les caractères sont des epsilon )(donc la séquence est délimitée par des epsilon);
• la tête de lecture/écriture est initialement positionnée sur le premier caractère de la séquence.

Remarquez bien qu'il n'est pas nécessaire que la séquence inversée occupe, sur la bande, la même position que la séquence initiale.

Testez votre machine sur un exemple simple (du moins dans un premier temps) !

Indications: si vous êtes en panne d'inspiration, vous pouvez essayer l'algorithme proposé ci-après.

1. Si la séquence d'entrée est vide, terminer. Sinon, aller jusqu'à la cellule immédiatement à droite de la frontière droite de la séquence, en mémorisant (dans la valeur des états : voir l'algorithme de parité ci-dessus) la valeur du dernier élément de la séquence.
2. Si la (nouvelle) séquence n'est pas vide, aller tout d'abord à sa frontière droite (toujours en mémorisant le dernier élément), puis écrire l'élément mémorisé (qui est alors le dernier élément de la nouvelle séquence), se déplacer à la fin de la séquence d'entrée courante, effacer son dernier élément et se déplacer à gauche. (Si la séquence n'est pas vide, on est alors de nouveau sur le dernier élément de la séquence d'entrée 'courante')
3. Si la séquence d'entrée courante est vide, aller à la frontière gauche de la nouvelle séquence et terminer. Sinon, aller au début de la nouvelle séquence en mémorisant le dernier caractère de la séquence d'entrée courante, puis recommencer en (2)