\documentclass{article} \usepackage[T1]{fontenc} \usepackage[latin1]{inputenc} \usepackage{geometry} \usepackage{turing} \usepackage{xspace} \usepackage[frenchb]{babel} \geometry{a4paper, left=1in,right=1in,top=1in,bottom=1in,nohead} \author{Jean-Côme Charpentier\\ email : \texttt{Jean-Come.Charpentier@wanadaoo.fr}} \title{{\LARGE \ttfamily turing (v. 0.4)}\\ Une simulation des machines de Turing avec \TeX} \date\today \begin{document} \maketitle \section{Présentation de la machine de Turing} \subsection{Un peu d'histoire} La machine de Turing a été conçu par \ldots Turing (Alan de son petit nom). Cette machine, à l'origine, était uniquement une machine théorique puisque les ordinateurs qui auraient pu la simuler n'existaient pas encore. En effet, la machine de Turing a été imaginée dans le cadre d'un travail sur une définition précise de la notion de preuve formelle au cours des années 1930 (en 1936 pour la machine de Turing). On peut qualifier d'apothéose de la machine de Turing la thèse de Turing-Church qui peut s'énoncer comme suit : \begin{quote} \itshape Toute fonction calculable l'est par une machine de Turing \end{quote} Comme un programme informatique peut être considéré comme une fonction calculable, il s'en suit que tout programme informatique peut être effectuée sur une machine de Turing. En ce sens, la machine de Turing est universelle. Avant d'en terminer avec les généralités, le lecteur pourrait se demander pourquoi on n'utilise pas de machines de Turing au lieu d'ordinateurs réels. Il y a deux raisons principales à cela : \begin{itemize} \item la machine de Turing est une machine idéale totalement impossible à obtenir (nous allons voir qu'elle fait appel à une bande d'écriture de longueur infinie ; \item même en prenant une machine de Turing finie, celle-ci se révèle désespéremment lente dans son fonctionnement. \end{itemize} \subsection{Anatomie et fonctionnement} Une machine de Turing est assez simple à décrire. Il s'agit d'un mécanisme comportant une bande (mettons de papier) de longueur infinie dans les deux sens, sur laquelle une tête de lecture/écriture se déplace. La bande est découpée en cellules. Les symboles qui peuvent se trouver sur la bande (un symbole par cellule) forme l'alphabet de la machine de Turing. Normalement, cet alphabet est quelconque mais on peut montrer qu'on peut toujours se ramener à un alphabet composé de deux symboles : ce sera le choix de l'extension \texttt{turing}. A tout instant, une machine de Turing se trouve dans un état déterminé. On notera cet état avec une suite de caractères (par exemple, l'état \texttt{i} ou bien l'état \texttt{A12}). Parmi ces états, deux vont avoir un rôle particulier : l'état initial qui est l'état de la machine de Turing avant que ses calculs ne commencent et l'état terminal qui est l'état qui indique que les calculs sont terminés\footnote{Là encore, une machine de Turing peut avoir plusieurs états terminaux possibles. On ne perd aucune généralité à décréter qu'il n'y en a qu'un seul. L'extension \texttt{turing} ne proposera qu'un seul état terminal.}. Enfin, une machine de Turing va évoluer selon des règles précises. Pour chaque état, et selon le symbole actuellement au niveau de la tête de lecture/écriture, la machine de Turing écrira un nouveau symbole à cet emplacement, changera d'état et déplacera la tête d'une cellule vers la gauche ou vers la droite. L'ensemble des règles consistera donc à préciser quoi faire lorsque la machine est dans un certain état en train de lire un certain symbole. Le \og quoi faire \fg étant quel symbole écrire, dans quel état devra se trouver la machine après cette écriture et dans quel sens devra se déplacer la tête de lecture. Un petit exemple pour fixer les idées. Supposons que l'état initial soit \texttt{i}, que l'état final soit \texttt{t}, qu'il n'y ait que les deux symboles $\bullet$ et $\langle$vide$\rangle$. Les règles sont décrites par le tableau ci-dessous : \begin{center} \begin{tabular}{|l|l||l|l|l|} \hline \multicolumn{1}{|c|}{\'Etat courant} & \multicolumn{1}{c||}{Symbole lu} & \multicolumn{1}{c|}{\'Etat de sortie} & \multicolumn{1}{c|}{Symbole écrit} & \multicolumn{1}{c|}{Déplacement} \\\hline \texttt{i} & $\bullet$ & \texttt{a} & \texttt{$\bullet$} & \texttt{r} \\\hline \texttt{i} & $\langle$vide$\rangle$ & \texttt{a} & $\bullet$ & \texttt{r} \\\hline \texttt{a} & $\bullet$ & \texttt{t} & $\bullet$ & \texttt{r} \\\hline \texttt{a} & $\langle$vide$\rangle$ & \texttt{a} & $\bullet$ & \texttt{r} \\\hline \end{tabular} \end{center} Ce \og programme \fg va laisser tranquille la première séquence de puces en la parcourant de gauche à droite et, dès qu'une cellule vide est rencontrée, on y écrit des puces. Le programme s'arrête lorqu'une nouvelle série de puces débute. Voici l'illustration de la chose. Supposons qu'on ait la bande initiale :\par \TuringInit{**....*.**}% \TuringCenterPrint où la flèche verticale représente la tête de lecture-écriture. Après l'exécution complète de ce programme on aura la situation suivante :\par \TuringTabState{i,*,i,*,r,% i,.,a,*,r,% a,*,t,*,r,% a,.,a,*,r}% \TuringRun \TuringCenterPrint \section{L'extension turing} \subsection{Préparation du terrain} Dans sa version actuelle, l'extension \texttt{turing} ne propose que les fonctions les plus importantes pour gérer une machine de Turing. Le codage a été effectué pour pouvoir servir aussi bien sous \LaTeX{} que sous \TeX. En revanche, bien qu'un certain nombre de tests ait été réalisés, il est tout à fait possible que des effets de bords nuisibles aient lieu sous certaines conditions d'utilisation. L'utilisateur scrupuleux n'hésitera pas à en faire part à l'auteur ! Comme il a été dit précédemment, les machines de Turing créées avec cette extension ne comporteront que deux symboles possibles, un seul état initial et un seul état terminal (on dit également état accepteur). \'Evidemment, la bande sera finie mais elle sera capable de s'agrandir automatiquement lorsqu'il le faudra. Commençons par les symboles. Le premier symbole sera toujours spécifié avec le caractères \texttt{*} par l'utilisateur mais sa présentation au niveau du document pourra être modifiée. Par défaut, il sagit du symbole \Tmark. Ce symbole est en fait stocké dans la macro \verb+\Tmark+ que l'on pourra modifier à volonté. Le second symbole disponible sera spécifié avec n'importe quel caractère (hormis \texttt{*}\footnote{Il faut également éviter les caractères actifs. Ainsi, avec les extensions de francisation, les caractères \og \string: \fg, \og \string; \fg, \og \string! \fg et \og \string? \fg deviennent interdits }). Au niveau du document, sa réprésentation est vide mais là encore, on peut modifier cette présentation par défaut en redéfinissant la macro \verb+\Tempty+. Enfin, le symbole de la tête de lecture/écriture et lui aussi modifiable via la macro \verb+\Thead+. Par exemple, avec la spécification suivante : \begin{verbatim} \def\Tmark{\oe} \def\Tempty{.} \def\Thead{$\uparrow$} \end{verbatim} le premier exemple de bande deviendrait :\par \begingroup \def\Tmark{\oe}% \def\Tempty{.}% \def\Thead{$\uparrow$}% \TuringInit{**....*.**}% \TuringCenterPrint \endgroup Pour terminer avec ces histoires de présentation, les dimensions des cellules ainsi que l'épaisseur des traits sont paramètrables avec les dimensions \verb+\Twidth+, \verb+\Theight+ et \verb+\Tthick+. Par exemple, avec la spécification suivante : \begin{verbatim} \Twidth=16pt % syntaxe TeX \setlength{\Theight}{8pt} % syntaxe LaTeX \Tthick=1pt \end{verbatim} le premier exemple de bande deviendrait :\par \begingroup \Twidth=16pt % syntaxe TeX \setlength{\Theight}{8pt} % syntaxe LaTeX \Tthick=1pt \TuringInit{**....*.**}% \TuringCenterPrint \endgroup Lorsqu'on veut gérer une machine de Turing, les deux premières étapes consistent à indiquer les symboles écrits sur la bande et à donner la table de transitions (le tableau de la page précédente). La liste des symboles sur la bande est spécifiée en utilisant la macro \verb+\TuringInit+ avec comme paramètre, une suite de caractères, les \texttt{*} de cette chaîne de caractères indiquant les emplacements des symboles \Tmark. La table de transition est donnée par la macro \verb+TuringTabState+ avec, comme paramètre, une suite de quintuplets de la forme : \texttt{<E\_entrée>,<S\_entrée>,<E\_sortie>,<S\_sortie>,<dir>} où \texttt{<E\_entrée>} indique l'état de départ et \texttt{<S\_entrée>} le symbole actuellement au niveau de la tête de lecture/écriture. Les trois autres données indiquent ce que dois faire la machine de Turing, à savoir se mettre dans l'état \texttt{<E\_sortie>} après avoir écrit le symbole \texttt{<S\_sortie>} puis déplacer sa tête de lecture/écriture dans la direction \texttt{<dir>}. La direction sera soit \texttt{r} ou \texttt{R} pour un déplacement vers la droite ou bien \texttt{l} ou \texttt{L} pour un déplacement vers la gauche. Chaque quintuplet sera séparé du suivant par une virgule\footnote{Tout ceci rend l'écriture de la teble de transitions un peu pénible. Une prochaine version de \texttt{turing} devrait améliorer ce point.}. Il faudra faire attention à ne pas mettre d'espace parasite au niveau de ce paramètre\footnote{Une prochaine version devrait permettre l'inclusion d'espace sans créer de problème.}. Une présentation permettant d'éviter les oublis peut être quelque chose du style : \begin{verbatim} \TuringInit{**....*.**}% \TuringTabState{i,*,i,*,r,% i,.,a,*,r,% a,*,t,*,r,% a,.,a,*,r}% \end{verbatim} C'est ce qui a été tapé dans ce document pour obtenir le premier exemple de programme. Pour visualiser la bande de la machine de Turing, il suffit de taper \verb+\TuringPrint+. Par défaut, cette macro ne crée pas de paragraphe et ne centre pas la bande. Si on veut obtenir une présentation hors-texte, on peut utiliser la macro \verb+\TuringCenterPrint+. Celle-ci réalise une présentation centrée en plaçant les espaces verticaux définis par les dimensions \verb+\Turingbeforeskip+ et \verb+\Turingafterskip+ (par défaut, ces deux valeurs sont fixées à \verb+\smallskip+). Enfin, la macro \verb+\TuringMoveIO+ permet de positionner la tête de lecture/écriture à n'importe quel endroit de la bande. Pour cela, il suffit de passer en paramètre l'indice de la cellule sur laquelle on veut que soit positionnée la tête de lecture/écriture. Lorsque la bande est crée avec \verb+\TuringInit+, la cellule de gauche est la cellule numéro~0 et la tête de lecture/écriture est positionnée à ce niveau, mais au cours des calculs, en cas d'allongement de la bande, cet indice peut devenir négatif. Voici un exemple complet pour montrer l'action des différentes macros : \begin{verbatim} \TuringInit{**.*..*mk*} \TuringPrint \TuringMoveIO{3} \TuringCenterPrint \end{verbatim} va donner :\medskip \TuringInit{**.*..*mk*} \TuringPrint \TuringMoveIO{3} \TuringCenterPrint \subsection{Calculs} L'extension \texttt{turing} met deux macros à disposition pour simuler le fonctionnement d'une machine de Turing : \verb+\TuringStep+ qui effectue un seul pas de calcul et \verb+TuringRun+ qui lance la machine jusqu'à ce qu'elle ait atteint son état terminal. Lorsqu'on crée une machine avec les macros \verb+\TuringInit+ et \verb+\TuringTabState+, elle se met automatiquement dans l'état initial. Cet état est l'état \texttt{i} par défaut. Cette valeur par défaut peut être modifiée en redéfinissant la macro \verb+\Tinit+. De même, il existe une valeur par défaut pour l'état final qui est l'état \texttt{t} et qu'on peut modifier en redéfinissant la macro \verb+Tterm+. Si on décide de modifier l'état initial, il faut obligatoirement le faire avant d'appeller la macro \verb+\TuringInit+. La macro \verb+\TuringStep+ permet d'effectuer un seul pas de calcul. Si la machine est dans l'état terminal, rien ne se passera et si la machine se trouve dans un état $e$ avec un symbole $s$ au niveau de la tête de lecture/écriture mais que la table de transition n'a pas prévu ce cas de figure, un message d'avertissement sera affiché sur le terminal et aucune action ne sera effectuée\footnote{Il est possible que dans une version ultérieure, on laisse le choix entre un message d'avertissement et un message d'erreur.}. En reprenant l'exemple donné au début de cette documentation, en tapant : \begin{verbatim} \TuringInit{**....*.**} \TuringCenterPrint \TuringTabState{i,*,i,*,r,% i,.,a,*,r,% a,*,t,*,r,% a,.,a,*,r} \TuringStep \TuringCenterPrint \TuringStep \TuringCenterPrint \TuringStep \TuringCenterPrint \TuringStep \TuringCenterPrint \end{verbatim} on obtient l'affichage suivant :\medskip \TuringInit{**....*.**} \null\hfill\TuringPrint\hfill\null\par \TuringTabState{i,*,i,*,r,% i,.,a,*,r,% a,*,t,*,r,% a,.,a,*,r} \TuringStep \TuringCenterPrint \TuringStep \TuringCenterPrint \TuringStep \TuringCenterPrint \TuringStep \TuringCenterPrint \bigskip La macro \verb+\TuringRun+ permet d'aller directement à la fin du calcul. \'Evidemment, si cette fin n'existe pas, la compilation va boucler indéfiniment. C'est donc à l'utilisateur de faire un peu attention à ce qu'il fait ! La macro \verb+\TuringRun+ peut être spécifiée avec un argument optionnel indiquant le nombre de pas de calcul maximum qui seront fait avant d'effectuer une pause. Ainsi, on aurait pu obtenir le dernier état de l'exemple précédent de façon direct avec le code : \begin{verbatim} \TuringInit{**....*.**} \TuringCenterPrint \TuringTabState{i,*,i,*,r,% i,.,a,*,r,% a,*,t,*,r,% a,.,a,*,r} \TuringRun[4] \TuringCenterPrint \end{verbatim} qui donnera :\medskip \TuringInit{**....*.**} \TuringCenterPrint \TuringTabState{i,*,i,*,r,% i,.,a,*,r,% a,*,t,*,r,% a,.,a,*,r} \TuringRun[4] \TuringCenterPrint \bigskip Il est possible de commencer un calcul avec la machine dans un état autre que l'état initial. Pour cela, il suffit de redéfinir la macro \verb+\Tstate+ après l'appel à la macro \verb+\TuringInit+. Attention : \verb+\TuringRun+ procède à des initialisations. Cette macro est sensée \emph{commencer} un calcul. Par conséquent, si on utilise cette macro avec un argument optionnel indiquant un nombre d'étapes maximum (syntaxe \verb+\TuringRun[<max>]+), la reprise du calcul ne devra pas se faire avec \verb+\TuringRun+. Pour reprendre un calcul interrompu, la macro à utiliser est \verb+\TuringResume+. Cette dernière fonctionne comme \verb+\TuringRun+, en particulier, elle admet également un paramètre optionnel indiquant un nombre maximum d'itérations. En, reprenant l'exemple précédant, cela pourrait donner : \begin{verbatim} \TuringInit{**....*.**} \TuringCenterPrint \TuringTabState{i,*,i,*,r,% i,.,a,*,r,% a,*,t,*,r,% a,.,a,*,r} \TuringRun[3] \TuringCenterPrint \TuringResume[2] \TuringCenterPrint \TuringResume \TuringCenterPrint \end{verbatim} qui donnera :\medskip \TuringInit{**....*.**} \TuringCenterPrint \TuringTabState{i,*,i,*,r,% i,.,a,*,r,% a,*,t,*,r,% a,.,a,*,r} \TuringRun[3] \TuringCenterPrint \TuringResume[2] \TuringCenterPrint \TuringResume \TuringCenterPrint \subsection{Améliorer l'affichage} La macro \verb+\TuringFormat+ supprime les séquences de cellules vides aux extrémités de la bande. Si la tête de lecture/écriture se trouve dans une zone supprimée, elle est déplacée sur la première cellule de la bande restante, sinon, elle reste sur la même cellule\footnote{Ce n'est peut être pas une bonne idée. Une autre possibilité serait d'interdire la suppression au-delà de la tête de lecture/écriture.}. Voici un petit exemple illustratif : \begin{verbatim} \TuringInit{..**.*.*...}% \TuringCenterPrint \TuringFormat \TuringCenterPrint \end{verbatim} donne :\par\medskip \TuringInit{..**.*.*...}% \TuringCenterPrint \TuringFormat \TuringCenterPrint La macro \verb+\TuringEnlarge+ permet d'agrandir la bande avec des cellules vides à droite et à gauche de la bande. Cette macro demande deux paramètres qui seront respectivement le nombre de cellules à ajouter à gauche et le nombre de cellules à ajouter à droite. Ces paramètres peuvent être des nombres négatifs auquel cas, la bande sera diminuée au lieu d'être augmentée. Voici un exemple : \begin{verbatim} \TuringInit{**..**.*.*.}% \TuringCenterPrint \TuringEnlarge{1}{2}% \TuringCenterPrint \TuringEnlarge{-4}{-3}% \TuringCenterPrint \end{verbatim} donne :\par\medskip \TuringInit{**..**.*.*.}% \TuringCenterPrint \TuringEnlarge{1}{2}% \TuringCenterPrint \TuringEnlarge{-4}{-3}% \TuringCenterPrint \section{Liste des choses à faire} La spécification de la table de transitions sans avoir le droit de mettre des espaces est un peu pénible. Il faudrait donc les permettre sans que cela interfère sur la lecture des arguments. Lorsqu'une bande est fabriquée, elle l'est dans une boîte horizontale. Cela signifie que si la bande est plus large qu'une ligne, elle sera composée dans la marge du document (pas terrible). Il faudrait donc un mécanisme automatique de découpage de la bande en cas de dépassement. Le mieux serait de distinguer si la compilation se fait sous \TeX{} ou sous \LaTeX{} pour tester la longueur du corps de texte respectivement avec \verb+\hsize+ ou \verb+\columnwidth+ (en cas de composition sur plusieurs colonnes). La spécification de la bande d'origine et de la table de transition est assez lourde, il faudrait prévoir la possibilité de lecture de ces données sur un fichier annexe par un \verb+\TuringRead{nom\_fichier}+. Il y a sans doute d'autres points qui peuvent être améliorés. Les critiques, suggestions, améliorations de toutes sortes seront hautement appréciées. \end{document}