Objectif.
L'objectif de ce tp est d'écrire un programme qui simule le fonctionnement d'une machine de Turing (Il faut noter qu'il s'agit indirectement d'une preuve que toute fonction T-calculable est ram-calculable) à la manière du simulateur fourni pour les séances de cours et de td. Comme pour les autres sujets, le langage choisi pour la réalisation est le langage C.
Sujet.
Le fichier exécutable devra s'appeler turing et recevoir sur la ligne de commande au moins deux paramètres :
Par convention, les fichiers programmes porteront l'extension .tur. La tête de lecture/écriture sera placée initialement sur le symbole le plus à gauche de la première chaîne. Par exemple, la commande turing fichier.tur TURING MACHINE indique que la séquence des instructions est contenue dans le fichier fichier.tur et que la bande doit être initialisée de la manière suivante (la tête de lecture/écriture est matérialisée par la case noire) :
| \( \) | \( \) | \( \) | \( \) | \( \) | \( \) | \( \) | \( \) | \(T\) | \(U\) | \(R\) | \(I\) | \(N\) | \(G\) | \( \) | \(M\) | \(A\) | \(C\) | \(H\) | \(I\) | \(N\) | \(E\) | \( \) | \( \) | \( \) |
| -8 | -7 | -6 | -5 | -4 | -3 | -2 | -1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
Les programmes pour la machine de Turing devront être contenus dans des fichiers textes comportant une seule instruction par ligne sous la forme \(q,\alpha : \omicron,q'\). Les caractères \(<\) et \(>\) seront utilisés pour coder le déplacement de la tête de lecture/écriture vers la gauche ou la droite respectivement. Les états pourront être représentés par une chaîne de caractères composées de chiffres ou de lettres. Les symboles autorisés pour la bande seront limités au chiffres et aux lettres et éventuellement quelques autres symboles (comme le point d'exclamation par exemple pour représenter le bâton de l'alphabet unaire).
Utilisez le programme flex pour filtrer le fichier programme et récupérer les instructions bien formées. Rappels : il faut l'option de compilation -lfl pour compiler le programme généré par flex (attention, il n'y a pas d'espace entre le -o et turing.c). Écrivez pour cela un fichier Makefile :
L'état initial de la machine de Turing sera par convention le premier état de la première instruction du programme (attention, la première instruction contenue dans le programme n'est pas nécessairement la première instruction qui sera exécutée par le programme !). L'alphabet de la machine de Turing sera déterminé a posteriori après la lecture du programme en récoltant tous les symboles en lecture et en écriture contenus dans les instructions du programme. Rajoutez éventuellement des paramètres à votre programme pour gérer le déroulement du programme de la machine de Turing (affichage du calcul pas-à-pas, direct, etc.)
pour afficher des caractères avec des couleurs en mode texte, utilisez les balises de la table ci-dessous. Par exemple, l'instruction
printf("\033[1;33m\033[40mVOTRE TEXTE ICI\033[0m");
affichera le texte en jaune sur fond noir :VOTRE TEXTE ICI
Cliquez sur le lien pour obtenir l'ensemble des codes couleurs. C'est la sous-chaîne 1;33 qui désigne la couleur du premier plan et la sous-chaîne 40 la couleur du fond.Conseils de programmation.
Pour représenter la bande de la machine de Turing, vous pouvez utiliser deux structures au choix:Dans le premier cas, pour indexer le tableau avec des entiers relatifs de manière à simuler les deux directions sur la bande vous utiliserez l'équipotence entre \(\mathbf N\) et \(\mathbf Z\) que nous avons démontrée en travaux dirigés à l'aide de la bijection \(f:{\mathbf N}\rightarrow{\mathbf Z}\) définie par :
\begin{equation} f(k)=\begin{cases} -(2k+1)&\text{si}\ k<0,\\ 2k&\text{sinon.} \end{cases} \end{equation} Il suffit donc d'écrire la fonction unsigned int ZN(int k) correspondante (ou de définir une macro avec un #define pour plus d'efficacité), de déclarer un tableau char * BANDE; et d'accéder à une cellule du tableau systématiquement à travers cette fonction, i.e. BANDE[ZN(k)]. La structure n'étant pas dynamique, il sera bien entendu nécessaire de faire un realloc pour augmenter la taille de la bande au fur et à mesure des besoins. La liste doublement chaînée reste néanmoins la structure la mieux adaptée à la nature séquentielle de la bande de la machine.Pour segmenter la chaîne de caractères yytext qui contiendra chaque instruction \(q,\alpha:o,q'\) du programme, vous écrirez une fonction char ** tranche(char *chaine, char car) qui renvoie un tableau de chaînes de caractères contenant les morceaux de la chaîne délimités par le caractère.