Exercice java machine de Turing : algorithme et POO de base

But:
Le but est d'écrire un programme permettant de simuler une machine de Turing.
Thème:
algorithme, 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):

Transition[][] table1 = {
// table pour le calcul de parit?
{new Transition(1,'0',+1), new Transition(1,'1',+1),new Transition(2,EPSILON,-1)},
{new Transition(3, EPSILON, -1), new Transition(4, EPSILON, -1),new Transition(UNDEF, EPSILON, -1)},
{new Transition(3, EPSILON, -1), new Transition(3, EPSILON, -1),new Transition(5, '1', +1)},
{new Transition(4, EPSILON, -1), new Transition(4, EPSILON, -1),new Transition(5, '0', +1)},
{new Transition(UNDEF, EPSILON, -1), new Transition(UNDEF, EPSILON, -1),new Transition(UNDEF, EPSILON, -1)}
};

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 :

Lancement de la machine de Turing
--------------------------------
Etat actuel : 1
Bande :
10
^ (Tete : 0)
--------------------------------
lu : 1, nouvel état : 1, écrit : 1, avance
--------------------------------
Etat actuel : 1
Bande :
10
^ (Tete : 1)
--------------------------------
lu : 0, nouvel état : 1, écrit : 0, avance
--------------------------------
Etat actuel : 1
Bande :
10
^ (Tete : 2)
--------------------------------
lu : e, nouvel état : 2, écrit : e, recule
--------------------------------
Etat actuel : 2
Bande :
10e
^ (Tete : 1)
--------------------------------
lu : 0, nouvel état : 3, écrit : e, recule
--------------------------------
Etat actuel : 3
Bande :
1ee
^ (Tete : 0)
--------------------------------
lu : 1, nouvel état : 3, écrit : e, recule
--------------------------------
Etat actuel : 3
Bande :
eee
^ (Tete : -1)
--------------------------------
lu : e, nouvel état : 5, écrit : 1, avance
--------------------------------
Etat actuel : 5
Bande :
1eee
^ (Tete : 1)
--------------------------------
lu : e, nouvel état : 0, écrit : e, recule
--------------------------------
Etat actuel : 0
Bande :
1eee
^ (Tete : 0)
--------------------------------
Arrêt de la machine de Turing.

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)

 


 

Fichiers:
Turing.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
// ----------------------------------------------------------------------
// Classes utiles
// ----------------------------------------------------------------------

class Tete {
private int position;

public Tete() {
position = Turing.POSITION_INITIALE;
}

public int getPosition() {
return position;
}

public void setPosition(int position) {
this.position = position;
}

public void avance() {
position++;
}

public void recule() {
position--;
}
}


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

public Transition(int etat, char caractere, int deplacement) {
this.etat = etat;
this.caractere = caractere;
this.deplacement = deplacement;
}

public int getEtat() {
return etat;
}

public char getCaractere() {
return caractere;
}

public int getDeplacement() {
return deplacement;
}
}

class TMachine {
private int etatActuel;
private String bande;
private Tete tete;
private Transition table [][];

public TMachine(Transition[][] table) {
etatActuel = Turing.ETAT_INITIAL;
bande = "";
tete = new Tete();
tete.setPosition(Turing.POSITION_INITIALE);
this.table = table;
}


/**
  * Réinitialise une machine et écrit les données d'entrée sur la bande.
  * @param entree Les données d'entrée
  */
public void reinitialise(final String entree) {
etatActuel = Turing.ETAT_INITIAL;
bande = entree;
tete.setPosition(Turing.POSITION_INITIALE);
}

/**
  * Lit le caractère courant sur une bande doublement infinie.
  * Simule l'aspect infini négatif en ajoutant un caractère en début de
  * chaîne puis en décalant la valeur de la tête (càd la remettre à 0)
  * @return Le caractère lu
  */
private char lecture() {
// simulation du ruban pour les positions négatives
while (tete.getPosition() < 0) {
bande = Turing.EPSILON + bande;
tete.avance();
}
// insertion des EPSILON nécessaires pour les position positives
while (tete.getPosition() >= bande.length()) {
bande = bande + Turing.EPSILON;
}
// lecture du caractère
return bande.charAt(tete.getPosition());
}

/**
  * Écrit un caractère sur une bande doublement infinie.
  * Simule l'aspect infini négatif en ajoutant un caractère en début de
  * chaîne puis en décalant la valeur de la tête (càd la remettre à 0)
  * @param Le caractère à écrire
  */
private void ecriture(char c) {
// simulation du ruban pour les positions négatives
while (tete.getPosition() < 0) {
bande = Turing.EPSILON + bande;
tete.avance();
}

// insertion des EPSILON nécessaires pour les positions positives
while (tete.getPosition() >= bande.length()) {
bande = bande + Turing.EPSILON;
}

// écriture du caractère
bande = bande.substring(0, tete.getPosition()) + c
+ bande.substring(tete.getPosition() + 1, bande.length());
}

/**
  * Affiche l'état de la machine de Turing
  */
private void affiche() {
System.out.println(" --------------------------------");
System.out.println(" Etat actuel : " + etatActuel);
System.out.println(" Bande :");
System.out.println(" " + bande);
System.out.print(" ");
for (int i = -1; i < tete.getPosition(); i++) {
System.out.print(" ");
}
System.out.println("^ (Tete : " + tete.getPosition() + ")");
System.out.println(" --------------------------------");
}

/**
  * Lance l'exécution de la machine de Turing
  */
public void lance() {
System.out.println("Lancement de la machine de Turing");
affiche();

while (etatActuel != UNDEF) {
// Cherche la position à lire dans la table de transition

// Indice de ligne
int i = etatActuel - 1;
// Indice de colonne (caractère lu)
System.out.print(" lu : " + lecture() + ",");
int j = 0;
switch (lecture()) {
case '0':
j = 0;
break;
case '1':
j = 1;
break;
case EPSILON:
j = 2;
break;
default:
System.out.println("ERREUR: j'ai lu un caractère inconnu: " + lecture());
affiche();
}

// Mise à jour de la machine
etatActuel = table[i][j].getEtat();
System.out.print(" nouvel état : " + etatActuel + ",");
ecriture(table[i][j].getCaractere());
System.out.print(" écrit : " + table[i][j].getCaractere() + ",");

switch (table[i][j].getDeplacement()) {
case 1:
tete.avance();
System.out.println(" avance");
break;
case -1:
tete.recule();
System.out.println(" recule");
break;
default:
System.out.println("ERREUR: déplacement inconnu: "
+ table[i][j].getDeplacement());
affiche();
}

affiche();
}

System.out.println("Arrêt de la machine de Turing.");
}

}


/**
 * Classe Principale
 */
class Turing {
public static final char EPSILON = 'e';
public static final int POSITION_INITIALE = 0;
public static final int UNDEF = 0;
public static final int ETAT_INITIAL = 1;

public static void main(String[] args) {
// Définit la table pour le calcul de parité
Transition[][] table1 = {
{new Transition(1, '0', +1), new Transition(1, '1', +1), new Transition(2, EPSILON, -1)},
{new Transition(3, EPSILON, -1), new Transition(4, EPSILON, -1), new Transition(UNDEF, EPSILON, -1)},
{new Transition(3, EPSILON, -1), new Transition(3, EPSILON, -1), new Transition(5, '1', +1)},
{new Transition(4, EPSILON, -1), new Transition(4, EPSILON, -1), new Transition(5, '0', +1)},
{new Transition(UNDEF, EPSILON, -1), new Transition(UNDEF, EPSILON, -1), new Transition(UNDEF, EPSILON, -1)}
};

// La table pour l'inversion des bits est donnée ci-après
// A vous de "l'injecter" dans votre programme dans le bon format
// voir table ci-dessus.
/* { { 2, '0', +1}, { 3, '1', +1}, {UNDEF, EPSILON, +1} },
  { { 2, '0', +1}, { 3, '1', +1}, { 4, EPSILON, +1} },
  { { 2, '0', +1}, { 3, '1', +1}, { 5, EPSILON, +1} },
  { { 4, '0', +1}, { 4, '1', +1}, { 6, '0', -1} },
  { { 5, '0', +1}, { 5, '1', +1}, { 6, '1', -1} },
  { { 6, '0', -1}, { 6, '1', -1}, { 7, EPSILON, -1} },
  { { 8, EPSILON, -1}, { 8, EPSILON, -1}, { 7, EPSILON, -1} },
  { { 10, '0', +1}, { 11, '1', +1}, { 9, EPSILON, +1} },
  { {UNDEF, '0', -1}, {UNDEF, '1', -1}, { 9, EPSILON, +1} },
  { { 4, '0', +1}, { 4, '1', +1}, { 10, EPSILON, +1} },
  { { 5, '0', +1}, { 5, '1', +1}, { 11, EPSILON, +1} }

  };*/


TMachine m = new TMachine(table1);
//m.reinitialise("10");
m.reinitialise("1101");
m.lance();
}
}

 

 

 

Lire aussi

  • Exercice java algorithme programme jeu de puissance 4
  • Exercice algo java tableaux, Modularisation et algorithme
  • Exercice programme java algorithme if boucle - L'heure du bilan -
  • Exercice Algorithme : Analyse (Cas Elections )
  • Exercice POO de base - trouver les erreurs
  • Exercice java sur les conversions entre les types de base entiers et doubles
  • Exercice algorithme java le plus grand diviseur commun
  • x