La machine de Turing

Vous trouverez sur cette page une brève introduction à la machine de Turing et un simulateur qui vous permettra de mettre à l'épreuve votre compréhension du modèle en testant vos propres pro­gram­mes.

Introduction

La machine de Turing est un modèle de machine abstrait introduit en 1936 par le chercheur anglais Alan Turing dans un article fondateur intitulé On Computable Numbers, With An Application To The Entscheidungsproblem dans lequel il propose une réponse à une question posée 8 ans plus tôt par le célèbre mathématicien David Hilbert. Il s'agit du problème de la décidabilité (en allemand "Entscheidungsproblem") soit en substance: existe-t-il un algorithme qui décide si une proposition énoncée dans un système logique est valide ou non ?

Pourquoi le modèle de calcul proposé par Alan Turing est-il devenu un outil indispensable en in­for­ma­ti­que fondamentale et en mathématiques ? Sa machine est en effet largement utilisée en théorie de la calculabilité, en théorie de la complexité ou en théorie de l'approximation. La raison principale tient à son extrême simplicité qui a permis d'établir des résultats sans nul doute beaucoup plus difficiles à démontrer avec des modèles moins rudimentaires. Cette machine est en fait le modèle le plus simple que l'on puisse concevoir et qui satisfait aux critères informels mais universels qui caractérisent un algorithme (déterminisme, discrétion, finitude, généralité, etc.)

Il faut noter que ce modèle, comme tant d'autres, a vu le jour à une époque où les ordinateurs tels que nous les connaissons aujourd'hui n'existaient pas, il s'agit donc avant tout d'un outil abstrait. La généralisation des ordinateurs dans les années 50-60 a donné naissance au modèle ram (Register Adressable Memory), plus proche de leur architecture physique et logique. Ce qui est remarquable, c'est que l'on a pu démontrer que tous ces modèles étaient équivalents. Ce que l'on peut calculer avec le modèle A peut l'être avec le modèle B et réciproquement.

Il est communément admis que tout modèle abstrait de calcul respectant les conditions informelles sur lesquelles les scientifiques s'accordent pour parler d'algorithme (si l'on excepte le calcul quantique qui définit un nouveau paradigme) aboutit à un modèle équivalent aux précédents. Ce résultat, appelé thèse de Church-Turing Alonzo Church est un ma­thé­ma­ti­cien américain in­venteur d'un autre mo­dè­le appelé λ-calcul ne peut évidemment pas être démontré puisque le concept d'algorithme est un concept informel. Un des objectifs du cours est de montrer l'équivalence des modèles de Turing et ram.

Il faut garder à l'esprit que la machine de Turing est un modèle universel de calcul et qu'elle peut calculer tout ce que n'importe quel ordinateur physique peut calculer (aussi puissant soit-il). In­ver­sement, ce qu'elle ne peut pas calculer ne peut l'être non plus par un ordinateur. Elle résume donc de manière saisissante le concept d'ordinateur et constitue un support idéal pour raisonner autour de la notion d'algorithme de calcul ou de démonstration.

Présentation de la machine.

Il existe différentes formulations de la machine de Turing, les deux que nous allons présenter ici correspondent aux plus courantes. En guise d'exercice d'application du cours, vous pourrez dé­mon­trer que ces deux modèles sont équivalents en terme de calculabilité.

Pour reprendre l'idée même d'Alan Turing, sa machine n'est rien d'autre qu'une version minimaliste de la machine à écrire que l'on pourrait contrôler à l'aide d'un programme. Une machine à écrire peut écrire ou effacer un symbole sur la feuille (même si l'effacement mécanisé avec un ruban correcteur n'était pas présent sur les premiers modèles), avancer ou reculer d'un ou plusieurs caractères. Au lieu d'opérer en deux dimensions sur une feuille de papier, la machine de Turing se contente d'une bande infinie à gauche et à droite et segmentée en cellules pouvant contenir chacune un symbole. Une tête de lecture/écriture remplace les barres à caractère physiques et agit sur la bande en suivant les règles du programme. Par commodité, on indexe souvent les cases de cette bande avec l'ensemble des entiers relatifs Z.

La bande joue à la fois le rôle de périphérique d'entrée et de sortie. Initialement vierge, on y inscrit à la main (virtuellement, c'est un modèle abstrait !) les données à traiter par le programme (entrée), qui sont des mots sur un alphabet Σ arbitraire mais fini. Par convention, on sépare les mots par une cellule vide et le premier symbole du premier mot est placé dans la cellule d'indice 0 où se trouve la tête de lecture/écriture. Pendant l'exécution du programme, la tête de lecture/écriture peut se déplacer à gauche ou à droite, lire le contenu de la cellule sur laquelle elle se trouve, l'effacer ou y écrire un symbole de Σ. À la fin de l'exécution du programme, les mots sur la bande constituent le résultat du calcul (sortie).

Avec l'alphabet \(\Sigma := \{a,b,...,z\}\) et l'entrée constituée des mots \(turing\) et \(machine\), la bande, dont on ne montre évidemment qu'une partie, contiendrait:

\( \) \( \) \( \) \( \) \( \) \( \) \( \) \( \) \(t\) \(u\) \(r\) \(i\) \(n\) \(g\) \( \) \(m\) \(a\) \(c\) \(h\) \(i\) \(n\) \(e\) \( \) \( \) \( \)
-8-7-6-5-4-3-2-1012345678910111213141516
Exemple de contenu de la bande de la machine.

La position de la tête de lecture/écriture est matérialisée ici par une cellule à fond noir.

Le fonctionnement est discret et ce que réalise la machine à chaque étape ne dépend que de deux paramètres : le symbole lu, c'est-à-dire celui qui est situé dans la cellule sur laquelle est placée la tête de lecture/écriture (le symbole \(t\) dans l'exemple ci-dessus), et l'état de la machine. Pour contrôler la machine, le programmeur dispose d'un ensemble fini d'états \(Q\) de son choix. Il fixe également l'état initial. C'est le programme qui va déterminer ce que la machine va faire en fonction du couple \((p,s)\) constitué par l'état courant de la machine et le symbole lu. Si la cellule est vide, on considère que le symbole lu est un symbole particulier appelé "blanc" et noté \(\square\).

Une première description du programme
Un programme est un ensemble de règles de la forme : \begin{equation}\label{eq:rule} \color{yellow}p,s:\omicron,q \end{equation} où \((p,s)\) est le couple condition et \((\omicron,q)\) le couple opération. On interprète la règle \((\ref{eq:rule})\) par :

"Si la machine est dans l'état \(\color{yellow}p\) et que le symbole lu est \(\color{yellow}s\), alors la machine exé­cute l'opération \(\color{yellow}\omicron\) et passe dans l'état \(\color{yellow}q\).
La machine étant déterministe, le programme ne peut évidemment contenir plus d'une règle avec le même couple condition \((p,s)\). Selon la valeur de \(o\), la machine fera un/une
  1. Écriture : si \(\omicron\in\Sigma\), le contenu de la cellule est écrasé par le symbole \(\omicron\) ;
  2. Effacement : si \(\omicron=\square\), le contenu de la cellule est effacé ;
  3. Déplacement : si \(\omicron\in\{\leftarrow,\rightarrow\}\), la tête de lecture/écriture se déplace vers la cellule à gauche ou à droite respectivement.
S'il n'existe pas de règle avec le couple condition (p,s), la machine s'arrête (arrêt).
Une machine de Turing est un sextuplet \((Q,\Sigma,\Gamma,q_0,\square,\delta)\) où
  1. \(Q\) est l'ensemble des états (fini) ;
  2. \(\Gamma\) est l'alphabet de travail (fini) ;
  3. \(\square\in\Gamma\) est un symbole particulier appelé symbole blanc ;
  4. \(\Sigma\subseteq\Gamma\setminus\{\square\}\) est l'alphabet d'entrée (fini) ;
  5. \(q_0\in Q\) est l'état initial ;
  6. \(\delta:Q\times\Gamma\rightarrow(\Gamma\cup\{\leftarrow,\rightarrow\})\times Q\) est la fonction de transition.

Une deuxième description du programme

Cette description est la plus commune, mais elle impose qu'à chaque règle appliquée, il y ait une opération d'écriture puis un déplacement. Cette fois une règle s'écrit: \begin{equation} \label{eq:rule2} \color{yellow}p,s:e,d,q \end{equation} On interprète la règle \((\ref{eq:rule2})\) par:
"Si la machine est dans l'état p, et que le symbole lu est s, alors elle écrit/efface selon e, se déplace selon la direction d et son nouvel état est q."
avec
  1. Écriture : si \(e\in\Sigma\), le contenu de la cellule est écrasé par le symbole \(e\) ;
  2. Effacement : si \(e=\square\), le contenu de la cellule est effacé ;
  3. Déplacement : selon que \(d=\leftarrow\) ou \(d=\rightarrow\), la tête de lecture/écriture se déplace vers la cellule à gauche ou à droite respectivement.
Comme pour la première description, s'il n'existe pas de règle avec le couple condition (p,s), la machine s'arrête (arrêt).
Une machine de Turing est un sextuplet \((Q,\Sigma,\Gamma,p_0,b,\delta)\) où
  1. \(Q\) est l'ensemble des états (fini) ;
  2. \(\Gamma\) est l'alphabet de travail (fini) ;
  3. \(\square\in\Gamma\) est un symbole particulier appelé symbole blanc ;
  4. \(\Sigma\subseteq\Gamma\setminus\{\square\}\) est l'alphabet d'entrée (fini) ;
  5. \(q_0\in Q\) est l'état initial ;
  6. \(\delta:Q\times\Gamma\rightarrow\Gamma\times\{\leftarrow,\rightarrow\}\times Q\) est la fonction de transition.

On rajoute parfois dans la définition un septième ensemble \(T\subseteq\Gamma\) dit des états terminaux ou finaux, c'est-à-dire des états dans lesquels la machine peut se trouver quand elle a fini son exécution. Ceci peut-être utile pour reconnaître des langages à la manière des automates. Par exemple, dans le cas de problèmes de décision, on définira classiquement \(T:=\{q_Y,q_N\}\), et on dira que \(q_Y\) est l'état d'acceptation et \(q_N\) est l'état de rejet. Le simulateur simule les deux modèles, le modèle à simuler étant déterminé automatiquement par la nature des règles contenues dans le fichier programme.

Définitions

Il devient clair à présent que le programme d'une machine de Turing n'est rien d'autre que le graphe de sa fonction de transition \(\delta\). C'est par simple commodité pour écrire les programmes que l'on écrit \(p,s:o,q\) plutôt que \(\delta(p,s)=(o,q)\). D'où la définition:

On appelle programme ou algorithme le graphe de la fonction de transition δ d'une machine de Turing.
On dit qu'un programme d'une machine de Turing s'arrête si sa fonction de transition \(\delta\) n'est pas définie pour le couple \((p,s)\) où \(p\) est l'état de la machine et \(s\) est le symbole lu.

Une bande \(B\) se modélise simplement, il s'agit d'un élément de \(\Gamma^{\mathbf Z}\), il est donc commode de désigner par \(B[k]\), à la manière des listes où des tableaux, le contenu de la cellule d'indice \(k\) (qui ici peut être négatif). Compte tenu des conventions établies pour l'utilisation de la machine de Turing, à chaque instant entre deux transitions, la bande est nécessairement vide de part et d'autre d'une zone utile, c'est-à-dire \begin{equation*} \exists (g,d)\in{\mathbf Z}\times{\mathbf Z},\ \ \forall i\in {\mathbf Z},\quad (i < g)\vee(i > d)\Rightarrow B[i] = \square \end{equation*} on représente donc son contenu par le mot de \(\Gamma^*\) constitué par la suite des symboles contenu dans les cellules d'indices \(g\) à \(d\) que l'on identifie au sous-tableau \(B[g\!:\!d]\). On peut alors définir ce qu'est une configuration.

On appelle configuration d'une machine de Turing, tout quadruplet \(C:=(q,u,i,h)\) de \(Q\times\Gamma^*\times{\mathbf Z}\times{\mathbf Z}\) où :
  1. \(q\in Q\) est l'état de la machine;
  2. \(u\in\Gamma^*\) est le mot contenu sur la bande;
  3. \(i\in{\mathbf Z}\) est la position du premier symbole de u sur la bande;
  4. \(h\in{\mathbf Z}\) est la position de la tête de lecture/écriture sur la bande.
On note \(C\Rightarrow C'\) si \(C\) est la configuration de la bande avant l'exécution d'une règle et \(C'\) est la configuration après l'exécution de cette règle. On peut surmonter le symbole \(\Rightarrow\) de la règle exé­cu­tée.

Avec les conventions établies, avant l'exécution d'un programme et avant que l'utilisateur n'ait saisi le mot d'entrée, la configuration de la machine est donc le quadruplet \((q_0,\epsilon,0,0)\) où \(\epsilon\) désigne le mot vide de \(\Gamma^*\). Une fois le mot \(u\in\Gamma^*\) saisi, la configuration est alors \((q_0,u,0,0)\).

Le diagramme des transitions permet de représenter graphiquement la fonction de transition. Il s'agit d'un multigraphe dont les sommets sont les états de la machine et les arcs représentent les transitions entre deux états. Les arcs sont étiquettés par le symbole lu et l'opération réalisée. Chaque machine ci-dessous est accompagnée de son diagramme des transitions. Le simulateur fournit ce diagramme au format dot de Graphviz une fois que le fichier programme a été chargé.

Exemples de programmes

Tous les programmes fournis ici peuvent être chargés puis exécutés sur ce simulateur écrit en javascript (et en php pour la lecture du fichier programme). Quand nous utiliserons l'alphabet unaire \(\Sigma=\{!\}\), l'unique symbole de Σ appelé bâton est représenté par un point d'exclamation. Dans ce cas l'ensemble des entiers naturels \({\mathbf N}\) est identifié au langage \(\Sigma^+\) grâce à la bijection \(\varphi:{\mathbf N}\rightarrow\Sigma^+\) définie par \(\varphi(n) :=\; !^{n+1}\) où la notation exponentielle est associée à l'opérateur de concaténation, par exemple \(!^3=\; !!!\) et \(!^0=\epsilon\), le mot vide.

On aurait pu choisir la bijection canonique \(\varphi:{\mathbf N}\rightarrow\Sigma^*\) définie par \(\varphi(n) :=\; !^{n}\), mais dans ce cas on ne pourrait pas distinguer 0 d'une cellule vide, en particulier pour des \(n\)-uplets d'entiers avec des fonctions définies ou à valeur dans \({\mathbf N}^k\). Par exemple le triplet d'entiers \((0,0,0)\) est codé par le mot \(\;!\;\square\;!\;\square\;!\) sur la bande.

Doubler le nombre de bâtons
Entrée: Une séquence de k bâtons sur la bande.
Sortie: Une séquence de 2k bâtons sur la bande.

Avec l'identification que nous nous sommes fixée entre N et Σ+, la machine calcule donc la fonction n ↦ 2n + 1. Initialement, la tête de lecture/écriture est sur le bâton le plus à gauche de la séquence initiale notée u = !k. Le principe général consiste à effacer successivement tous les bâtons de u par la gauche et pour chaque bâton effacé d'en rajouter deux à une séquence v initialement vide.

Plus précisément, la bande contient initialement !k. On efface le premier bâton de u, et on l'écrit au bout de la séquence v initialement vide et située à gauche de la séquence u. La bande contient alors !□!k - 1. On parcourt tous les bâtons de v vers la gauche (à cette étape v n'en contient qu'un) et on inscrit le second bâton au début de v. La bande contient donc !!□!k - 1. On se replace à gauche de la séquence u qui ne contient plus que k - 1 bâtons et on recommence jusqu'à ce que tous les bâtons de u soient effacés. Le programme suivant réalise ces opérations:

# DOUBLE LE NOMBRE DE BATONS (CARACTERE !) SUR LA BANDE # BLOC 1: TEST u CONTIENT-T-IL ENCORE UN BÂTON ? S,!: ,A # OU!, on l'efface puis BLOC 2 S, :<,T # NON: on va à gauche puis BLOC 3 # BLOC 2: EFFACER UN BÂTON DE u ET EN RAJOUTER DEUX A v A, :<,B # On va a gauche de la cellule qu'on vient d'effacer B, :!,C # On ecrit un premier bâton à droite de v C,!:<,C # On saute tous les bâtons de v vers la gauche C, :!,D # On ecrit le deuxième bâton à gauche de v D,!:>,D # On saute tous les bâtons de v vers la droite D, :>,S # On saute la cellule vide entre v et u et on recommence # BLOC 3: REVENIR SUR LE PREMIER BÂTON DE v ET FIN T, :<,U # On déplace la tete sur le bâton le plus a droite de v U,!:<,U # On saute tous les bâtons de v vers la gauche U, :>,F # On revient sur le premier bâton de v. C'est fini
Diagramme des transitions de cette machine.

Calculer la fonction de N → N × N définie par n ↦ (n,n)
Entrée: Une séquence de k := n + 1 bâtons.
Sortie: deux séquences de k bâtons séparés par une cellule vide.

L'algorithme consiste à initialiser à un bâton une séquence v à gauche de u en séparant v et u par une cellule vide. Puis on efface un à un les n premiers bâtons de la séquence u qui en contient initialement n + 1. Pour chaque bâton effacé de u, on le rajoute à gauche de v. Une fois qu'il ne reste plus que le dernier bâton à la séquence u, on remplit les n + 1 cellules vides séparant v et u, on recrée la cellule séparatrice pour arriver finalement à !k□!k.

# CALCULE LA FONCTION n -> (n,n) de N dans N x N # BLOC 1: ECRIRE PREMIER BATON DE v ET REVENIR SUR PREMIER BATON DE u D,!:<,I0 # On va à gauche de u sur le blanc separateur I0, :<,I1 # On saute le blanc séparateur entre u et v à gauche I1, :!,I2 # On écrit le premier baton de v I2,!:>,I3 # On revient sur le separateur I3, :>,U # On se place sur le premier bâton de u. Puis BLOC 2 # BLOC 2: RESTE-T-IL UN AUTRE BATON A DROITE DU PREMIER SYMBOLE DE u ? U,!:>,T # On va à droite du premier baton de u. T,!:<,E0 # OUI => on va a gauche puis copier cf. BLOC 3 T, :<,F0 # NON => on va a gauche et on finit cf. BLOC 5 # BLOC 3: EFFACER LE "PREMIER" BATON DE u ET L'ECRIRE A GAUCHE DE v E0,!: ,E1 # on efface le premier baton de u E1, :<,E1 # on saute tous les blancs entre u et v vers la gauche E1,!:<,G # on saute le dernier baton de v vers la gauche G,!:<,G # puis tous les autres batons de v vers la gauche G, :!,R # on écrit un baton de plus a gauche de v # BLOC 4: REVENIR SUR LE "PREMIER" BATON DE u R,!:>,R # on saute tous les batons de v vers la droite R, :>,S # on saute le blanc separateur entre v et u S, :>,S # on saute tous les blancs de u S,!:!,U # on recommence au bloc 2 # BLOC 5: IL NE RESTE QU'UN BATON DANS u, ON FINIT F0,!:<,F1 # on va a gauche de u et F1, :!,F0 # on remplit les cellules F1,!:>,F2 # on a rempli tout l'espace F2,!: ,F2 # on efface pour recreer la cellule separatrice F2, :<,F3 # on va a gauche F3,!:<,F3 # on saute les batons de v vers la gauche F3, :>,F # on revient sur le premier baton de v, c'est fini.
Diagramme des transitions de cette machine.

Calculer la fonction de N × N → N définie par (a,b) ↦ a + b. (addition)
Entrée: Une séquence de k := a + 1 bâtons suivie d'une séquence de l := b + 1 bâtons.
Sortie: Une séquence de a + b + 1 bâtons.

L'algorithme est extrêmement simple, la bande contient initialement !k□!l et il suffit de placer le symbole ! dans la cellule vide qui sépare les deux séquences de k batôns et de l bâtons (!k+l+1) et d'effacer les deux bâtons à gauche de la séquence de k + l + 1 bâtons ainsi constituée.

# CALCULE LA FONCTION (a,b) -> a + b de N x N dans N # BLOC 1: ECRIRE LE BÂTON ENTRE LES DEUX SÉQUENCES D,!:>,D # on saute les k premiers bâtons vers la droite D, :I,1 # on remplace le blanc central par un bâton, puis BLOC 2 # BLOC 2: ON REVIENT à GAUCHE POUR EFFACER LES DEUX BÂTONS EN EXCÉDENT. 1,!:<,1 # on ramène la tête de L/E sur le blanc à gauche 1, :>,2 # on avance sur le premier bâton 2,!: ,2 # on efface le premier bâton 2, :>,3 # on avance 3,!: ,4 # on efface le second bâton 4, :>,F # on avance d'une cellule.
Diagramme des transitions de cette machine.

Calculer la fonction de N × N → N définie par (a,b) ↦ a × b. (produit)
Entrée: Une séquence de k := a + 1 bâtons suivie d'une séquence de l := b + 1 bâtons.
Sortie: Une séquence de a × b + 1 bâtons.

L'algorithme consiste, pour chacun des a premiers bâtons de la première séquence u (qui en contient a + 1 au départ), de recopier les b premiers bâtons de la seconde séquence v (qui en contient b + 1 au départ) au bout d'une troisième séquence w initialement vide. Cette copie se fait en effaçant successivement les b premiers bâtons de v et en les recopiant au bout de w, le dernier bâton de v sert à contrôler la fin de la copie après laquelle on reconstitue les b bâtons effacés pendant la copie. Une fois qu'il ne reste qu'un bâton à u, la séquence w en contient a × b, on peut alors terminer. On efface le dernier bâton de u ainsi que les b + 1 bâtons de v et on rajoute un dernier bâton à la séquence résultat w.

# CALCULE LA FONCTION (a,b) -> a x b de N x N dans N # BLOC 1: RESTE T-IL AU MOINS DEUX BATONS DANS u ? A,!:>,U1 # RESTE-T-IL 2 BATONS ? On va a droite du premier baton de u U1,!:<,U2 # OUI => on revient sur le premier U2,!: ,U3 # et on l'efface. Puis BLOC 2 pour aller au debut de v U1, :<,F0 # NON => BLOC 8 pour finir la construction de w # BLOC 2: DEPLACEMENT VERS LE PREMIER BATON DE v U3, :>,U4 # On saute la case de u qui vient d'être effacee U4,!:>,U4 # On saute tous les batons de u vers la droite U4, :>,V0 # On saute le blanc separateur entre u et v. Puis BLOC 3 # BLOC 3: RESTE T-IL AU MOINS DEUX BATONS DANS v ? V0,!:>,V1 # RESTE-T-IL 2 BATONS ? On va a droite du premier baton de v V1,!:<,V2 # OUI => on revient sur le premier V2,!: ,S0 # et on l'efface. Puis BLOC 4 se deplacer au bout de w V1, :<,E0 # NON => il faut reecrire les batons effacés de v # BLOC 4: DEPLACEMENT A DROITE DE w S0, :>,S1 # On saute la cellule qui vient d'etre effacee S1,!:>,S1 # On saute tous les batons de v S1, :>,S2 # On saute le blanc separateur entre v et w S2,!:>,S2 # On saute tous les batons de w S2, :!,R0 # On rajoute un baton a w. Puis BLOC 5 pour revenir sur v # BLOC 5: RETOUR SUR v R0,!:<,R0 # On revient a gauche de w R0, :<,R1 # On revient a gauche du blanc separateur entre v et w R1,!:<,R1 # On revient a gauche de v R1, :>,V0 # BLOC 6: REECRITURE DES BATONS DE v E0,!:<,E1 # On passe a gauche du dernier baton de v E1, :!,E2 # On remplit les vides entre u et v E2,!:<,E1 # tant qu'il en reste E1,!:>,E3 # On est sur le baton au bout de u, on va a droite E3,!: ,T0 # On recrée le blanc separateur entre u et v. Puis BLOC 7 # BLOC 7: RETOUR A GAUCHE DE u T0, :<,T1 # Saut à gauche du blanc separateur entre u et v T1,!:<,T1 # Saut à gauche de u T1, :>,A # Retour sur le premier baton de u. Puis BLOC 1. # BLOC 8: FIN. Effacement de u et v puis ecriture du dernier de w F0,!: ,F1 # Effacement du dernier baton de u F1, :>,F2 # On va sur le blanc separateur entre u et v F2, :>,F3 # On saute le separateur entre u et v F3,!: ,F4 # OUI il reste des batons à effacer dans v ? F4, :>,F3 # On va à droite et on recommence. F3, :!,Z # NON, on ecrit le dernier baton de w.
Diagramme des transitions de cette machine.

Décider si un entier est multiple de 4?
Entrée: un entiers n en binaire.
Sortie: Aucune. La réponse est OUI si la machine s'arrête dans l'état OUI, NON si elle s'arrête dans l'état NON.

Cette fois nous utilisons le deuxième modèle de machine de Turing comme une machine décisionnelle, les états d'acceptation qY et de refus qN sont tous simplement représentés par les chaînes "OUI" (l'entier est multiple de 4) et "NON" (l'entier n'est pas multiple de 4) dans le programme. On suppose que l'alphabet est binaire, i.e. Σ :={0,1}.

Initialement, la tête de lecture/écriture doit être sur le bit de poids fort de n. Le principe est simple, pour que n soitmultiple de 4, il faut et il suffit que ces deux derniers bits de poids faible soient égaux à 0.

# DECIDE SI UN EN BINAIRE ENTIER EST UN MULTIPLE DE 4 # BLOC 0: ON SE PLACE SUR LE BIT DE POIDS FAIBLE D,1:1,>,D # on saute tous les bits vers la droite D,0:0,>,D D, :<,L0 # On se place sur le bit de poids faible # BLOC 2: ON TESTE LE BIT DE POIDS FAIBLE L0,0:<,L1 # Il est egal a 0, on passe a l'avant dernier L0,1:1,NON # Il vaut 1, le nombre n'est pas multiple de 4 # BLOC 3: ON TESTE LE DEUXIEME BIT DE POIDS FAIBLE L1,0:0,OUI # Il est egal a 0, le nombre est multiple de 4 L1,1:1,NON # IL vaut 1, le nombre n'est pas multiple de 4
Diagramme des transitions de cette machine.

Multiplier un entier représenté en binaire par 2
Entrée: un entiers n en binaire.
Sortie: Aucune. La réponse est OUI si la machine s'arrête dans l'état OUI, NON si elle s'arrête dans l'état NON.

Nous utilisons encore le deuxième modèle de machine de Turing. On suppose que l'alphabet est binaire, i.e. Σ :={0,1}. Il suffit de rajouter un 0 après le bit de poids faible de n.

# CALCULE LA FONCTION n -> 2 x n OU n EST EN BINAIRE # BLOC 0: LA BANDE EST-ELLE VIERGE ? S, : ,>,F # OUI: ON VA A DROITE ET FIN DU PROGRAMME S,0:0,>,T # NON: ON VA A DROITE ET ON CONTINUE S,1:1,>,T # NON: ON VA A DROITE ET ON CONTINUE # BLOC 1: ON SAUTE A DROITE DE LA SEQUENCE T,0:0,>,T T,1:1,>,T # BLOC 2: ON RAJOUTE UN 0 T, :0,<,U # ON RAJOUTE 0 ET ON VA A GAUCHE U,0:0,<,U # ON SAUTE A GAUCHE LA NOUVELLE SEQUENCE U,1:1,<,U # IDEM U, : ,>,F # ON REVIENT SUR LE BIT DE POIDS FORT ET FIN
Diagramme des transitions de cette machine.