Retour

turing.tex

Télécharger le fichier 
%% BEGIN: turing.tex
%%
%% Turing est un package permettant de simuler
%% une machine de Turing.
%%
\def\fileversion{0.4}
\def\filedate{2003/01/20}
%%
%% COPYRIGHT 2003 by Jean-C\^ome Charpentier
%%
%% This program can be redistributed and/or modified under the terms
%% of the LaTeX Project Public License Distributed from CTAN
%% archives in directory macros/latex/base/lppl.txt.
%%
\csname TuringLoaded\endcsname
\let\TuringLoaded\endinput
\newif\ifTuring@LaTeX
\edef\PstAtCode{\the\catcode`\@}
\catcode`\@=11\relax
\expandafter\ifx\csname @latexerr\endcsname\relax
  \Turing@LaTeXtrue
  \long\def\@ifundefined#1#2#3{%
    \expandafter\ifx\csname#1\endcsname\relax#2\else#3\fi}
  \def\typeout#1{\immediate\write\@unused{#1}}
  \alloc@7\write\chardef\sixt@@n\@unused
  \def\@empty{}
  \def\@ifnextchar#1#2#3{%
    \let\@tempe#1\def\@tempa{#2}\def\@tempb{#3}\futurelet\@tempc\@ifnch}
  \def\@ifnch{%
  \ifx\@tempc\@sptoken
    \let\@tempd\@xifnch
  \else
    \ifx\@tempc\@tempe \let\@tempd\@tempa \else \let\@tempd\@tempb \fi
  \fi
  \@tempd}
  \begingroup
  \def\:{\global\let\@sptoken= } \:
  \def\:{\@xifnch} \expandafter\gdef\: {\futurelet\@tempc\@ifnch}
  \endgroup
\fi
\typeout{`Turing' v\fileversion\space\space <\filedate> (jcc)}
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Valeurs par défaut des paramètres généraux %%%
%%% gérant le fonctionnement et l'affichage    %%%
%%% de la machine de Turing.                   %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcount\T@Max     % indice max sur la bande
\newcount\T@Min     % indice min sur la bande
\newcount\T@oldMax  % sauvegarde temporaire
\newcount\T@oldMin  % sauvegarde temporaire
\newcount\T@Current % compteur interne
\newcount\T@IO      % emplacement de la tête d'E/S
 
\newdimen\Twidth \Twidth = 24pt   % largeur d'une cellule
\newdimen\Theight \Theight = 18pt % hauteur d'une cellule
\newdimen\Tthick \Tthick = 0.4pt  % épaisseur des traits
 
\def\Tmark{$\bullet$}  % symbole de marque
\def\Tempty{}          % symbole de vide
\def\Thead{$\bigm\Uparrow$}
 
\def\Tinit{i}  % état initial
\def\Tstate{i} % état courant de la machine
\def\Tterm{t}  % état final
 
\def\Turingbeforeskip{\smallskip} % espace avant une bande centrée
\def\Turingafterskip{\smallskip}  % espace après une bande centrée
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% \TuringInit initialise une bande de Turing %%%
%%%                                            %%%
%%% le paramètre est une suite de caractères   %%%
%%% tels que '*' représente une marque et      %%%
%%% tout autre caractère représente un vide.   %%%
%%%                                            %%%
%%% En fin de macro, \T@Min vaut zéro,         %%%
%%% \T@Max indique l'indice du dernier symbole %%%
%%% spécifié et \T@IO est positionné en 0.     %%%
%%%                                            %%%
%%% La bande est mémorisée dans les macros     %%%
%%% privées \T@band<n> où <n> indique l'indice %%%
%%% de la cellule.                             %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\TuringInit{\begingroup
  \catcode`\.=11 % évite les problèmes de terminaisons
  \Turing@Init}
\def\Turing@Init#1{\global\T@Max=0 \global\T@Min=0 \global\T@IO=0
  \xdef\Tstate{\Tinit}%
  \@TURinit#1. \global\advance\T@Max by -1 \endgroup}
 
\def\@TURinit#1#2.{\def\next@param{#2}%
  \if*#1
    \expandafter\gdef\csname T@band \the\T@Max \endcsname{*}%
  \else
    \expandafter\gdef\csname T@band \the\T@Max \endcsname{.}%
  \fi
  \global\advance\T@Max by 1
  \ifx \empty\next@param
    \let\next\relax
  \else
    \let\next\@TURinit
    \edef\next@param{\next@param.}%
  \fi
  \expandafter\next\next@param}
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% \TuringTabState permet de spécifier la     %%%
%%% table de transition. Le paramètre à        %%%
%%% transmettre est une suite de quintuplets   %%%
%%% sous la forme :                            %%%
%%%   <ec>,<sl>,<ef>,<se>,<dir>                %%%
%%% où <ec> indique l'état courant             %%%
%%%    <sl> indique le symbole lu              %%%
%%%    <ef> indique l'état final               %%%
%%%    <se> indique le symbole écrit           %%%
%%%    <dir> indique la direction de la tête   %%%
%%% chaque quintuplet est séparé du suivant    %%%
%%% par une virgule.                           %%%
%%%                                            %%%
%%% Le début des calculs se fait dans l'état   %%%
%%% Tinit (par défaut "i") et les calculs      %%%
%%% s'arrêtent lors de la machine se met dans  %%%
%%% l'état Tfinal (par défaut "t").            %%%
%%%                                            %%%
%%% On notera qu'il est facile d'obtenir des   %%%
%%% boucles infinies : c'est à l'utilisateur   %%%
%%% de faire attention le cas échéant !        %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\TuringTabState{\begingroup
  \catcode`\.=11 % évite les problèmes de terminaison
  \T@TS}
\def\T@TS#1{\T@@TS#1,.\endgroup}
\def\T@@TS#1,#2,#3,#4,#5,#6.{%
  \def\next@param{#6}%
  \expandafter\gdef\csname TS@#1@#2@\endcsname{#3,#4,#5}%
  \ifx\next@param\empty
    \let\next\relax
  \else
    \let\next\T@@TS
    \edef\next@param{\next@param.}%
  \fi
  \expandafter\next\next@param}
 
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% \TuringStep effectue une opération         %%%
%%% élémentaire sur la bande de Turing.        %%%
%%%                                            %%%
%%% La macro lit la bande au niveau de \T@IO   %%%
%%% et, en fonction de l'état courant (placé   %%%
%%% dans \Tstate), écrit la nouvelle valeur    %%%
%%% sur la bande, place la machine dans son    %%%
%%% nouvel état et déplace la tête de          %%%
%%% lecture/écriture.                          %%%
%%%                                            %%%
%%% Si aucune spécification de la table        %%%
%%% d'état ne correspond au couple (symbole,   %%%
%%% état courant), un message d'erreur est     %%%
%%% affiché.                                   %%%
%%%                                            %%%
%%% Si le déplacement fait sortir de la bande  %%%
%%% actuelle, la bande est agrandie d'une      %%%
%%% cellule.                                   %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\TuringStep{%
  \edef\Tsymb{\csname T@band \the\T@IO \endcsname}% symbole lu
  \expandafter\ifx\csname TS@\Tstate @\Tsymb @\endcsname\relax
    \ifx\Tstate\Tterm
      % pas de message d'erreur sur l'état terminal
    \else
      \immediate\write16{Turing error : state (\Tstate) with symbol %
        (\Tsymb) not defined in state table.}%
    \fi
    \let\next\relax
    \def\next@param{}%
  \else
    % appel de \T@write avec <état final>,<symb final>,<dir>
  \let\next\T@write
  \expandafter\edef\expandafter\next@param{%
    \csname TS@\Tstate @\Tsymb @\endcsname}%
  \fi
  \expandafter\next\next@param}
\def\T@write#1,#2,#3{% écriture de :
  \gdef\Tstate{#1}% état
  \expandafter\gdef\csname T@band \the\T@IO \endcsname{#2}% symbole
  % déplacement de la tête et vérification
  \ifx r#3
    \ifnum\T@IO=\T@Max
      \TuringEnlarge{0}{1}%
    \fi
    \global\advance\T@IO by 1
  \else \ifx R#3
    \ifnum\T@IO=\T@Max
      \TuringEnlarge{0}{1}%
    \fi
    \global\advance\T@IO by 1
  \else \ifx l#3
    \ifnum\T@IO=\T@Min
      \TuringEnlarge{1}{0}%
    \fi
    \global\advance\T@IO by -1
  \else \ifx L#3
    \ifnum\T@IO=\T@Min
      \TuringEnlarge{1}{0}%
    \fi
    \global\advance\T@IO by -1
  \fi\fi\fi\fi}
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% \TuringRun permet de lancer l'éxecution de %%%
%%% la machine de Turing.                      %%%
%%%                                            %%%
%%% On peut passer, en argument optionnel, le  %%%
%%% nombre de pas maximum avant l'arrêt.       %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\TuringRun{\xdef\Tstate{\Tinit}\@ifnextchar[{\T@Run}{\T@Run[-1]}}
\def\T@Run[#1]{%
  \global\T@Current=#1 % nombre de pas à effectuer
  \T@@Run}
\def\T@@Run{%
  \ifnum\T@Current=0
    \let\next\relax
  \else
    \ifnum\T@Current<0
      \let\next\T@@@Run
    \else
      \let\next\T@@@Run
      \global\advance\T@Current by -1
    \fi
  \fi
  \next}
\def\T@@@Run{%
  \TuringStep % effectue un pas
  \ifx\Tstate\Tterm
    \let\next\relax % arrêt sur l'état terminal
  \else
    \let\next\T@@Run % sinon recommence
  \fi
  \next}
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% \TuringResume permet de relancer           %%%
%%% l'exécution de la machine de Turing.       %%%
%%%                                            %%%
%%% On peut passer, en argument optionnel, le  %%%
%%% nombre de pas maximum avant l'arrêt.       %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\TuringResume{\@ifnextchar[{\T@Run}{\T@Run[-1]}}
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% \TuringPrint imprime la bande de Turing en %%%
%%% cours.                                     %%%
%%%                                            %%%
%%% La bande commence en \T@Min et va jusqu'à  %%%
%%% \T@Max. La tête d'E/S est positionnée à    %%%
%%% \T@IO.                                     %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\TuringPrint{%
  \T@Current=\T@Min
  \setbox0=\hbox{\vrule width\Tthick height\Theight}%
  \loop
    \expandafter\if\csname T@band \the\T@Current \endcsname *%
      % la cellule contient un symbole non vide
      \setbox0=\hbox{\box0
        \hbox to\Twidth{\hss\vbox to\Theight{\vss\hbox{\Tmark}\vss}\hss}%
        \vrule width\Tthick height\Theight}%
    \else
      % la cellule contient un symbole vide
      \setbox0=\hbox{\box0
        \hbox to\Twidth{\hss\vbox to\Theight{\vss\hbox{\Tempty}\vss}\hss}%
        \vrule width\Tthick height\Theight}%
    \fi
  \ifnum\T@Current<\T@Max \advance\T@Current by 1
  \repeat
  \dimen0=\Twidth              % position de la tête = 
  \advance\dimen0 by\Tthick    % largeur d'une cellule (avec réglure)
  \count@=\T@IO
  \advance\count@ by-\T@Min    % nombre de cellules
  \multiply\dimen0 by\count@   % largeur de toutes les cellules
  \advance\dimen0 by\Tthick    % + réglure de départ
  \advance\dimen0 by0.5\Twidth % + 1/2 cellule
  \setbox0=\hbox{\vbox{\hrule width0pt height2pt
    \hrule height\Tthick \box0 \hrule height\Tthick
    \hbox to\dimen0{\hss\vbox{\hbox to0pt{\hss\Thead\hss}}}}}%
  \setbox1=\vbox{\hbox{\Thead}}%
  \dimen0=\dp1 \advance\dimen0 by \ht1 \advance\dimen0 by 2pt
  \leavevmode\lower\dimen0\box0}
 
\def\TuringCenterPrint{\par\Turingbeforeskip\noindent
  \ifTuring@LaTeX
    \hbox to\columnwidth{\hss\TuringPrint\hss}%
  \else
    \hbox to\hsize{\hss\TuringPrint\hss}%
  \fi
  \par\Turingafterskip\noindent}
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% \TuringMoveIO déplace la tête de           %%%
%%% lecture/ecriture à la position spécifiée.  %%%
%%%                                            %%%
%%% En cas de déplacement en dehors des        %%%
%%% limites de la bande, on affiche un         %%%
%%% message d'erreur et rien n'est fait.       %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\TuringMoveIO#1{%
  \ifnum\T@Max<#1
    \immediate\write16{Turing warning : IO out of range (too big)}%
    \global\T@IO=\T@Max
  \else \ifnum\T@Min>#1
    \immediate\write16{Turing warning : IO out of range (too small)}%
    \global\T@IO=\T@Min
  \else
    \global\T@IO=#1
  \fi\fi}
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% \TuringFormat permet de faire commencer    %%%
%%% la bande à la première cellule non vide    %%%
%%% et de la terminer à la dernière cellule    %%%
%%% non vide. Cette macro accepte deux         %%%
%%% arguments optionnels indiquant les         %%%
%%% positions gauche et droite à partir        %%%
%%% desquelles s'effectue la recherche.        %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\TuringFormat{%
  \@ifnextchar[{\Turing@Format}{\Turing@Format[\the\T@Min]}}
\def\Turing@Format[#1]{%
  \@ifnextchar[{\Turing@@Format[#1]}{\Turing@@Format[#1][\the\T@Max]}}
\def\Turing@@Format[#1][#2]{%
  \T@Current=#1
  \advance\T@Current by-1
  \loop
    \advance\T@Current by 1
    \expandafter\if\csname T@band \the\T@Current \endcsname .%
  \repeat
  \global\T@Min=\T@Current
  \T@Current=#2
  \advance\T@Current by 1
  \loop
    \advance\T@Current by -1
    \expandafter\if\csname T@band \the\T@Current \endcsname .%
  \repeat
  \global\T@Max=\T@Current
  \ifnum\T@IO<\T@Min \global\T@IO=\T@Min \fi
  \ifnum\T@IO>\T@Max \global\T@IO=\T@Max \fi}
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% \TuringEnlarge ajoute des cellules vides   %%%
%%% de chaque côté de la bande (#1 pour la     %%%
%%% gauche et #2 pour la droite).              %%%
%%%                                            %%%
%%% La position de la tête de lecture/écriture %%%
%%% est déplacée pour rester au niveau de la   %%%
%%% même cellule.                              %%%
%%%                                            %%%
%%% Il est possible de fournir des valeurs     %%%
%%% négatives et la macro vérifiera que la     %%%
%%% largeur finale soit au moins égale à 1.    %%%
%%% Si la tête de lecture était positionnée    %%%
%%% sur une partie supprimée, elle est alors   %%%
%%% placée en début de bande visible.          %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\TuringEnlarge#1#2{
  \T@oldMin=\T@Min
  \T@oldMax=\T@Max
  \global\advance\T@Min by -#1
  \global\advance\T@Max by #2
  \ifnum\T@Min>\T@Max
    \global\T@Max=\T@Min
  \fi
  \ifnum\T@IO<\T@Min
    \global\T@IO=\T@Min
  \fi
  % créations éventuelles des \T@band@<num>
  \T@Current=\T@Min
  \loop
    \expandafter\ifx\csname T@band \the\T@Current \endcsname \relax
      \expandafter\gdef\csname T@band \the\T@Current \endcsname{.}
    \fi
  \ifnum\T@Current<\T@Min \advance\T@Current by 1
  \repeat
  \T@Current=\T@Max
  \loop
    \expandafter\ifx\csname T@band \the\T@Current \endcsname \relax
      \expandafter\gdef\csname T@band \the\T@Current \endcsname{.}
    \fi
  \ifnum\T@Current>\T@Max \advance\T@Current by -1
  \repeat}
 
\catcode`\@=\PstAtCode\relax
%
\endinput
%%
%% END: turing.tex