École polytechnique — X2010 — INF423 Fondements de l’informatique

Machines de Turing
Sujet proposé par Bruno Salvy
(corrigé)

Les machines de Turing sont un de ces sujets qui paraissent simples et ennuyeux à la lecture,
mais qui s’avèrent subtils et intéressants si l’on essaye de les construire par soi-même. L’objectif
de ce sujet est de faire appréhender par la construction “manuelle” la puissance d’expressivité de
ce modèle, et donc de comprendre pourquoi l’adhésion à la thèse de Church est si universelle.

Définition. Le point de départ sera la définition du polycopié, rappelée ici :

Une machine de Turing est un octuplet M = (Q, Σ, Γ, B, δ, q0 , qa , qr ) où
– Q est l’ensemble fini des états ;
– Σ est un alphabet fini ;
– Γ ⊃ Σ est l’alphabet de travail fini ;
– B ∈ Γ \ Σ est le caractère blanc ;
– q0 , qa , qr sont des éléments de Q appelés état initial, état d’acceptation, état de refus ;
– δ : Q × Γ → Q × Γ × {←, →} est la fonction de transition.

Notations. Une machine de Turing sera définie graphiquement par un graphe dont les sommets
sont les états, les arcs représentant les transitions. Une transition δ(q1 , `) = (q2 , m, d), où q1 , q2
sont dans Q, les lettres `, m dans Γ et d est une direction sera représentée par une étiquette `/md
sur l’arc reliant le sommet q1 au sommet q2 . Pour alléger les figures, on ajoute trois conventions :
– dans le cas où m = `, on se contentera de l’étiquette `d ;
– lorsqu’existent plusieurs transitions du type précédent entre deux mêmes états, on étiquet-
tera l’arc `1 , `2 , . . . d ;
– les arcs pointant vers l’état de refus ne seront pas représentés.
Par exemple, voici une représentation de la machine de Turing acceptant les mots n’utilisant
que les lettres a et b de Σ :
a,b →

q0 qa
B→

Sous-programmes. On s’efforcera de programmer les machines de Turing de façon modulaire,

en réutilisant des machines déjà écrites. Pour cela, une machine sera symbolisée par l’un des deux
schémas
qa

q0 M q0 qa
M

qr

selon que la transition vers l’état de refus est réutilisée pour pointer vers un autre état ou non.
L’utilisation de machines comme sous-programmes impose une spécification très précise de
leurs droits. Ainsi, sauf indication contraire, les machines de Turing n’écriront jamais à gauche

1
de la position initiale de leur tête de lecture, le mot donné en entrée sera toujours borné par un
B à gauche et à droite, et lorsqu’une machine de Turing s’arrêtera sur son état d’acceptation, sa
tête de lecture sera d’abord revenue à sa position initiale.

1 Mots et Langages
1.1 Langages rationnels
Les machines de Turing restreintes dont les transitions sont toutes de la forme δ(q1 , `) =
(q2 , `, →) sont classiquement appelées automates finis déterministes. Elles reconnaissent des lan-
gages appelés rationnels, dont l’exercice suivant donne un exemple typique.

Question 1.1. Écrire une machine de Turing acceptant les mots sur l’alphabet Σ = {a, b} qui
contiennent le sous-mot aab et se terminent par un b, et refusant tous les autres mots sur Σ.

Solution : La machine suivante effectue ce travail :

b→ a→ b→

a→
a→ b→ B→
q0 q1 q2 q3 qa

b→
a→

La lecture s’effectue depuis l’état initial q0 jusqu’à l’état d’acceptation qa . Tant que la machine
ne rencontre pas le premier a, elle avance sa lecture et reste sur son état initial. Dès qu’un
premier a est rencontré, elle passe dans l’état q1 , qu’elle quitte vers q2 si un deuxième a suit le
premier, alors qu’elle doit retourner en q0 sinon. Une fois le sous-mot aa rencontré, la machine
reste dans l’état q2 tant qu’elle ne lit pas un b, qui lui permet d’arriver en q3 . À ce stade, il ne
reste plus qu’à attendre le b final, c’est-à-dire le sous-mot bB, ce qui se traduit par des aller-
retours entre q2 et q3 en attendant la fin du mot. Les transitions vers l’état de refus ne sont pas
indiquées. Elles ont lieu lorsqu’une lettre ne correspondant pas à une transition indiquée est lue,
c’est-à-dire pour cette machine si la lettre B est lue dans l’un des états q0 , q1 , q2 .

Les langages rationnels servent à exprimer les “expressions régulières” qui sont utilisés dans
de nombreux éditeurs de texte pour effectuer de la recherche avancée. Ne pouvant ni écrire, ni
revenir en arrière, ces automates sont incapables de reconnaître des langages dont les mots ont
une structure de dépendance à longue portée, mais permettent des recherches très rapides et avec
peu de mémoire dans de très grand textes comme le génome.

1.2 Déplacements sur le ruban

La programmation de machines de Turing pousse à déplacer fréquemment la tête de lecture
sur le ruban, par exemple jusqu’aux extrémités. Les deux sous-routines suivantes seront donc
très utiles.

Question 1.2. Écrire une machine de Turing Fx (pour Forward) qui avance la tête de lecture sur
le ruban jusqu’à la première occurrence de la lettre x ∈ Γ et recule alors sur le caractère précédent.
Cette machine refuse les mots qui ne contiennent pas x. Écrire de même la fonction symétrique
Bx (pour Backward) qui recule et termine sur le premier caractère suivant l’occurrence de x
précédente.

Solution : La machine Fx avance sa tête de lecture tant qu’elle ne lit pas de x, et va dans l’état
d’acceptation dès qu’elle en rencontre un. La transition vers l’état de refus qui n’est pas indiquée
se produit lorsque le mot ne contient pas la lettre x, ce qui est détecté en lecture d’un blanc
en q0 , sauf si x = B. Il y a une petite difficulté puisque x est supposé appartenir à Γ et non Σ,

2
ce qui entraine un traitement spécial pour B afin d’éviter que la machine ne boucle au lieu de
refuser. La machine Bx est obtenue comme miroir de Fx en renversant les flèches.
Γ\{x,B}→ Γ\{x,B}←

q0 qa q0 qa
x← x→

1.3 Langages context-free

Les langages de programmation ne sont pas des langages rationnels, mais sont souvent
“context-free”, c’est-à-dire une généralisation des langages rationnels, qui permet de reconnaître
des mots bien parenthésés (penser à des begin. . .end ou if . . .fi ). Pour les reconnaître, il est crucial
de pouvoir écrire sur le ruban.

Question 1.3. Écrire une machine de Turing acceptant les mots sur l’alphabet {a, ), (} qui ont
le même nombre de parenthèses fermantes que de parenthèses ouvrantes, et dont aucun facteur
gauche (sous-mot démarrant à la première lettre) ne possède plus de parenthèses fermantes que
d’ouvrantes. (Indication : on peut effacer le mot initialement présent sur le ruban).

Solution : Il y a (au moins) deux variantes correspondant à des algorithmes de natures diffé-
rentes. Dans la première variante ci-dessous, la machine efface des paires de parenthèses qui se
correspondent dans le mot. La tête de lecture cherche la première parenthèse fermante à partir du
début du mot, la remplace par un a et repart en arrière à la recherche de la parenthèse ouvrante
correspondante, qu’elle remplace à son tour par un a, avant de revenir à l’état initial. Lorsque la
fin du mot est atteinte, pour vérifier que le mot ne comportait pas un excédent de parenthèses
ouvrantes, le mot est balayé en reculant pour s’assurer qu’il n’y reste que des a avant d’accepter.
Les refus se produisent soit en lecture d’une parenthèse ouvrante en q2 (parenthèse qui n’est
pas refermée), soit en lecture d’une parenthèse fermante en q0 (parenthèse qui n’en referme pas
d’autre).
a←
q1

)/a← (/a→

q0 q2 qa

(,a→ a←

Dans la seconde variante ci-dessous, la machine se contente de maintenir le nombre de paren-

thèse ouvrantes supérieur ou égal au nombre de parenthèses fermantes dans les facteurs gauches.
La tête de lecture efface tous les caractères jusqu’à la première parenthèse ouvrante incluse en
les remplaçant par des blancs, puis va chercher la première parenthèse fermante et la remplace
par un a avant de revenir au début de ce qui reste du mot. Lorsque le mot est complètement
effacé, la machine accepte. Les refus se produisent soit en lecture d’une parenthèse fermante
en q0 (parenthèse qui n’en referme pas d’autre), soit en lecture d’un blanc en q1 (fin de mot
prématurée).

3
 q1
(/B→

B→ a/B→ )/a←
qa q0

BB

1.4 Copies et effacements

Question 1.4. Écrire deux machines D et D0 (pour delete) qui prennent en entrée un mot `w
où ` ∈ Σ = {a, b} et w est un mot sur Σ, et s’arrêtent avec le mot w sur leur ruban. Il faut
donc décaler d’une lettre toutes les lettres de w. La machine D termine avec sa tête de lecture sur
le premier caractère de w, alors que D0 termine avec sa tête de lecture sur le premier caractère
suivant w, et ne devra pas supposer que le premier caractère à gauche de ` est un blanc.

Solution : Là encore, il y a plusieurs façons de procéder. La première machine D ci-dessous

commence par aller à la fin du mot (par FB ), efface le dernier caractère en le mémorisant par son
choix de branche (vers q2 si c’est un a, vers q3 si c’est un b), puis décale le mot d’un caractère
en passant de q2 à q3 selon la lettre précédente. Elle termine en atteignant le blanc précédant le
début du mot.
a←

q2
B→
a/B←

q0 FB q1 a/b← b/a← qa

b/B← B→
q3

b←

La seconde variante fonctionne pour D et D0 . La tête de lecture saute le premier caractère,

lit le suivant, puis recule pour l’écrire à la place du précédent, et recommence jusqu’à rencontrer
la fin du mot. À ce stade, soit elle s’arrête en acceptant, ce qui donne D0 (à gauche). Soit elle
revient au début du mot, ce qui donne D (à droite).
q2

a←

q0 q1 q4 q0 D' BB qa

b←

qa q3

Question 1.5. Écrire une machine D` qui prend en entrée un mot sur Σ et en efface tous les
caractères jusqu’au premier ` ∈ Σ inclus.

4
Solution : Il suffit d’utiliser la machine précédente.
q1 D

Σ\ →

q0 qa

q1 D

Question 1.6. À l’inverse, écrire trois machines I` , I0` et I00` (pour insert) qui prennent en entrée
un mot w sur l’alphabet {a, b}, et s’arrêtent avec respectivement les mots `w, w`, w` sur leurs
rubans. La différence entre I0` et I00` est que cette dernière laisse sa tête de lecture sur le caractère
suivant w`.

Solution : L’insertion en fin de mot par I00` (à gauche ci-dessous) est assez simple, et I0` (à droite)
s’en déduit :
Σ→ B/ →
q0 FB q1 qa q0 I' BB qa

La tête de lecture est emmenée d’abord sur la dernière lettre du mot, puis un caractère plus loin
où le ` est inséré, avant de ramener la tête de lecture sur la première lettre dans le cas de I0 ` .
La machine I` , comme D et D0 , mémorise par le contrôle de la machine les lettres à copier :
a→

q1
a/ → B/a→

q0 a/b→ b/a→ q3 BB qa

b/ → B/b→
q2

b→

Question 1.7. Écrire une machine Copym ` qui prend un mot de la forme w1 `w2 où w1 et w2
sont des mots sur Σ = {a, b}, ` et m sont des lettres différentes de B dans Γ \ Σ, et s’arrête avec
le mot w1 `w2 mw1 sur son ruban.

Solution : Une difficulté est, en cours de copie, de mémoriser la partie du mot déjà copiée. Voici
deux solutions.
La machine ci-dessous propage un blanc. Les transitions vers q1 exploitent le fait que la
machine I0 ramène la tête de lecture sur le premier caractère suivant le blanc précédent. Enfin,
les deux dernières transitions suppriment le décalage d’un blanc introduit par cette construction.

5
 Β/a→
q2 q3
Β→

a/Β← I'a

q0 IB I'm q1 BB D' qa

b/Β← I'b

Β→
Β/b→
q4 q5

La seconde variante étend l’alphabet de travail par des lettres a0 , b0 et remplace les lettres
copiées par leur version ‘primée’ au fur et à mesure, avant de les nettoyer à la fin. La machine Ba0 ,b0
qui y est employée comme sous-routine est une variante de B qui cherche plusieurs lettres à la
fois (obtenue en remplaçant x par a0 , b0 dans la machine Bx ).
q2 I''a

a/a'→

q0 I'm q1 q5 Ba',b'

b/b'→

q3 q4 I''b

qa

2 Arithmétique
Jusqu’ici les calculs se sont limités à des manipulations élémentaires sur des mots. Une ma-
nière simple de se convaincre qu’il est possible d’effectuer des calculs arithmétiques avec une
machine de Turing est de programmer les fonctions récursives primitives de la semaine dernière !
Le k-uplet d’entiers (n1 , . . . , nk ) sera représenté par le mot an1 +1 ban2 +1 b · · · ank +1 . (On aurait
pu aussi prendre des 0 et des 1, mais il sera plus facile de réutiliser les machines précédentes sur
cet alphabet.)

2.1 Zéro
Question 2.1. Écrire une machine de Turing prenant en entrée le codage d’un entier et s’arrê-
tant avec le codage de 0 (On dira qu’elle calcule 0).

Solution :
a,b/B→

q0 a→ q1 Ba qa

6
2.2 Successeur
Question 2.2. Écrire une machine de Turing qui calcule la fonction prenant en entrée un en-
tier n et renvoyant n + 1.

Solution : La machine est Ia .

2.3 Projection
Question 2.3. Écrire une machine de Turing Proji qui calcule la fonction prenant en entrée un
k-uplet d’entiers et renvoyant le ie, avec 1 ≤ i ≤ k.

Solution : On distingue le cas de Proj1 des autres, qui se définissent récursivement :

Db

q0 Fb BB qa q0 Db Proji-1 qa

2.4 Composition
Question 2.4. À partir de k machines G1 , . . . , Gk calculant des fonctions g1 , . . . , gk de Nn dans N
et d’une machine F calculant une fonction f de Nk dans N, construire une machine calculant
l’application (x1 , . . . , xn ) 7→ f (g1 (x1 , . . . , xn ), . . . , gk (x1 , . . . , xn )).

Solution : L’idée est d’aller calculer les fonctions g1 , . . . , gk dans cet ordre, de plus en plus à
droite sur le ruban, en insérant un blanc pour que les machines Gi n’effacent pas ce qui a déjà
été calculé. On utilise une machine auxiliaire CopyArgs pour recopier les arguments (x1 , . . . , xn )
derrière un blanc :
q0 Copycc FB Bc q1 qa

Cette machine prend en entrée un mot de la forme w1 cw2 , où w1 codera les arguments x1 , . . . , xn ,
elle le transforme d’abord en w1 cw2 cw1 , puis en w1 cw2 Bw1 et laisse la tête de lecture positionnée
sur le premier caractère du w1 final.
La composition se résume alors ainsi :
q0 I'c CopyArgs G1 D' BB

CopyArgs G2 D' BB

CopyArgs Gk D' BB Dc F qa

7
En tout début de calcul, la machine transforme l’argument w en wc, puis appelle la machine pré-
cédente pour obtenir wcBw avant d’appeler G1 qui termine avec le mot wcBg1 (w), ensuite la tête
de lecture est ramenée sur le blanc, qui est effacé par D0 avant de ramener la tête de lecture tout
au début du mot wcg1 (w). La deuxième étape commence par transformer ce mot en wcg1 (w)Bw
avant de lancer l’appel à G2 . En dernière ligne, on a donc obtenu le mot wcg1 (w) · · · gk (w). La
machine Dc efface tout le début du mot jusqu’à c, et il ne reste plus qu’à appeler F.

2.5 Récursivité
Question 2.5. À partir d’une machine G calculant une fonction g de Nn−1 dans N et d’une
machine H calculant une fonction h de Nn+1 dans N, construire une machine calculant la fonction
de Nn dans N définie récursivement par

f (0, x2 , . . . , xn ) = g(x2 , . . . , xn ),
f (x1 + 1, x2 , . . . , xn ) = h(f (x1 , . . . , xn ), x1 , . . . , xn ).

Solution :

q0 a→ q1 q2 BB I'c CopyArgs D

q3 BB D D G

D' qa

BB CopyArgs BB D' BB Dc H

Pour mémoriser l’état antérieur, cette machine procède comme la machine Comp en allant
travailler plus à droite sur le ruban. La première opération consiste à tester si x1 = 0. La
première transition lit un premier a, et le branchement est effectué par q1 . La première ligne de
la machine traite le cas où x1 6= 0, en transformant le mot w qui code (x1 , . . . , xn ) en wcBw0 où
w0 code (x1 − 1, x2 , . . . , xn ) grâce au D final. La machine repart alors en q0 . Lorsque la transition
vers q2 a finalement lieu, le ruban contient le mot

wx1 cBwx1 −1 cB · · · cBw0 c,

où wi code (i, x2 , . . . , xn ), et la tête de lecture est sur le premier caractère du x2 de w0 (ou sur B
si n = 1). La deuxième ligne de la machine calcule alors g(x2 , . . . , xn ) après avoir effacé x1 = 0.
Ensuite, il faut aller dépiler les valeurs précédentes de xn . Lorsque la machine arrive à la
sortie de la machine D0 de la 3e ligne et que le calcul n’est pas terminé, le ruban contient le mot

wx1 cBwx1 −1 cB · · · cBwi cv,

où v code f (i − 1, x2 , . . . , xn ). La dernière ligne transforme alors la portion wi cv en wi cvwi puis

vwi , ce qui code f (i − 1, x2 , . . . , xn ), x2 , . . . , xn et permet d’appeler H, de sorte qu’à la sortie de
la ligne, wi cv est remplacé par f (i, x2 , . . . , xn ). Ceci permet de recommencer tant qu’il reste un c
à gauche, c’est-à-dire tant que la pile n’est pas vide. Ensuite, il y a un blanc à gauche et le calcul
est terminé.

8
2.6 Minimisation non-bornée
Les machines de Turing ont donc au moins l’expressivité des fonctions récursives primitives.
Le sujet de la semaine dernière se concluait en mentionnant que ce qui manquait aux fonctions
primitives récursives pour avoir toute l’expressivité des machines de Turing était la minimisation
non-bornée (correspondant au ‘while’ des langages de programmation). C’est par contre une
opération très facile à implanter sur une machine de Turing.

Question 2.6. À partir d’une machine F calculant une fonction f : Nn → {0, 1}, construire une
machine, qui prend en entrée le codage de (x2 , . . . , xn ) et s’arrête avec sur son ruban le codage
du plus petit y ∈ N tel que f (y, x2 , . . . , xn ) = 1 s’il en existe 1, et boucle sinon.

Solution :
q0 Ib Ia I'c DB q1 DB qa

a→
CopyArgs F

Ia DB

Cette machine commence par insérer le codage de 0 en tête de ruban, puis elle ajoute un c
à la fin de son entrée ainsi modifiée. Ensuite, elle utilise CopyArgs pour recopier le codage de
(0, x2 , . . . , xn ) après un espace au-delà de ce c. La machine F est alors invoquée sur cet argument.
Si elle réussit, alors le résultat est effacé, puis la tête de lecture est amenée juste après la fin
de y et le reste du ruban est effacé. Si elle échoue, alors le résultat est effacé aussi, puis y est
incrémenté (par Ia ) et le calcul reprend.