Calculabilité et Complexité – TD 2 –

TD 2 - Machines de Turing
Dans ce TD, on considère des machines opérant sur un ruban semi-infini (indexé par les entiers naturels).
On note # le symbole case vide, et on suppose que la configuration initiale associée au mot w d’une machine
ayant comme état initial q0 est q0 #w : autrement dit le pointeur est initialement sur la première case du ruban,
qui est initialement laissée vide.

Première partie – Manipulation du ruban

Exercice 1. Déplacements sur le ruban

Question 1. - Avancer jusqu’à un symbole - Soit Σ = {a, b, ℓ} un alphabet d’entrée. Écrire une machine de
Turing Aℓ qui avance la tête de lecture jusqu’à la première occurence du symbole ℓ, puis recule pour se placer
sur la case immédiatement à gauche. Cette machine refuse les mots qui ne contiennent pas le symbole ℓ.
Solution :

a/a, ·
b/b, ·

#/#, · ℓ/ℓ, ¶
i 0 1

Question 2. - Remplacer - Soit Σ = {a, b, c} l’alphabet d’entrée. Écrire une machine Ra,b qui échange les
a et les b du mot d’entrée (en laissant les c inchangés) et qui s’arrète sur la première case du ruban.
Solution :

a/b, · a/a, ¶
b/a, · b/b, ¶
c/c, · c/c, ¶

#/#, · #/#, ¶ #/#, »

i 0 1 2

Exercice 2. Copies et effacements

On fixe pour cet exercice l’alphabet Σ = {a, b}. Les symboles ℓ et w seront utilisés respectivement pour
dénoter un symbole de Σ et un mot de Σ⋆ .
Question 1. - Effacer - Écrire une machine E qui, en partant d’un ruban #ℓw, s’arrète avec le ruban #w.
Solution :

a/a, ¶
a/a, ·
b/b, · a/#, ¶ ?/a, ¶
2a
a/?, ·
#/#, · b/?, · #/#, ¶
i 0 1 2 b/a, ¶ a/b, ¶ 3

2b
b/#, ¶ ?/b, ¶

b/b, ¶

Paul Brunet 1/9

Calculabilité et Complexité – TD 2 –

Question 2. - Effacer jusqu’à un symbole - Écrire une machine Eℓ qui efface toutes les lettres de son entrée
jusqu’au premier ℓ ∈ Σ inclus.

Solution :
On donne la solution suivante dans le cas où ℓ = a.
?/?, ¶ #/#, ·
a/a, ·
b/b, ·
2a 3a
a/a, ¶
b/?, · ?/?, · ?/#, ¶ b/b, ¶
#/#, ¶
a/?, ¶ ?/a, · a/a, ¶
#/#, · b/b, ¶ #/#, ·
i 0 1 3 4 5
a/?, · #/#, ¶
b/?, ¶ ?/b, ·

2b 3b
#/#, ·
a/a, ·
?/?, ¶ b/b, ·

Le cas ℓ = b se traite de la même manière, en échangeant a et b dans les deux transitions sortant de
l’état 0. Ainsi on effacera tous les a jusqu’à croiser le premier b.

Question 3. - Insérer - Écrire trois machines Iℓ , I′ℓ , et I′′ℓ qui prennent en entrée un mot w ∈ Σ⋆ (donc un
ruban #w) et s’arrètent respectivement avec les rubans #ℓw, #wℓ, et #wℓ#.

Solution :
Machine Iℓ
a/a, ·

a/a, ¶
a/?, · #/a, ¶ b/b, ¶
1a

#/#, · ?/ℓ, ¶
i 0 b/a, · a/b, · 1 2

1b
b/?, · #/b, ¶

b/b, ·

Machine I′ℓ
a/a, · a/a, ¶
b/b, · b/b, ¶

#/#, · #/ℓ, ¶ #/#, »

i 0 1 2

Machine I′′ℓ
a/a, ·
b/b, ·

#/#, · #/ℓ, ·
i 0 1

Paul Brunet 2/9

Calculabilité et Complexité – TD 2 –

Question 4. - Copier - Soit Γ un alphabet de travail contenant Σ, et ℓ, m ∈ Γ \ (Σ ∪ {#}) deux symboles

ℓ qui prend en entrée un mot w1 ℓw2 , avec w1 , w2 ∈ Σ , et s’arrète avec le
⋆
de travail. Écrire une machine Cm
ruban #w1 ℓw2 mw1 .
Solution :

a/a, · a/a, · a/a, ·

b/b, · b/b, · b/b, ·
a/a, ¶
b/b, ¶
m/m, · ℓ/ℓ, ¶
a/A, · ℓ/ℓ, · #/m, · #/a, ¶ m/m, ¶
i 1a 2a 3a
#/#, ·

0 1
ℓ/ℓ, ¶
m/m, ·
a/a, ¶ b/B, · ℓ/ℓ, · #/m, · #/b, ¶
b/b, ¶ 2 1b 2b 3b

#/#, »
a/a, · a/a, · a/a, ·
b/b, · b/b, · b/b, ·
3
A/a, ·
B/b, ·

Deuxième partie – Reconnaissance de langages

Exercice 3. Langage mystère

Quel est le langage sur l’alphabet Σ = {a, b, c} reconnu par la machine suivante ?

c/z, ¶ b/b, ·
q6 q0 q4 q3
a/a, ¶ z/z, ·
b/b, ¶
y/y, ¶
#/#, » #/#, · z/z, ¶ b/y, ·
#/#, » x/x, ·

y/y, · q5 q1 q2 a/a, ·
z/z, · y/y, · a/x, · y/y, ·

Exercice 4. Langages réguliers

Question 1. - Sous-mot - É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).
Solution :

a/a, · a/a, ·
b/b, · b/b, ·

#/#, · a/a, · a/a, · b/b, · #/#, ¶ b/b, ·

i 0 1 2 3 4 5

Paul Brunet 3/9

Calculabilité et Complexité – TD 2 –

Question 2. Écrire une machine de Turing acceptant le langage Ja⋆ ba⋆ bK.
Solution :

a/a, · a/a, ·

#/#, · b/b, · b/b, · #/#, ¶

i 0 1 2 3

Question 3. Écrire une machine de Turing acceptant le langage

 ⋆
w ∈ {a, b, c} w contient abc mais pas bb .

Solution :
Le langage demandé est un langage régulier, on peut donc le reconnaître avec un automate à états finis.
Voici un tel automate :
a a, c
b
c a c
a ab abc
a
c
ε a b b a, c
c
b
b b bb b′
b

On peut ensuite transformer cet automate en machine de Turing, en applicant les modifications suivantes :
— on ajoute un nouvel état initial i et un nouvel état final ok ;
x x/x,·
— chaque transition p −
→ q est remplacée par p −−−→ q ;
#/#,·
— on ajoute une transition i −−−→ ε, et pour chaque état final de l’automate q ∈ F, on ajoute une
#/#,¶
transition q −−−→ ok.
On obtient ainsi la machine suivante :
a/a, ·
a/a, · c/c, ·
b/b, ·
c/c, · a/a, · c/c, · #/#, ¶
a ab abc
c/c, ·
#/#, · a/a, ·
ε a/a, · b/b, · b/b, · a/a, ·
i c/c, · ok
c/c, · b/b, ·
b/b, · b bb b′
b/b, · #/#, ¶

On peut également reconnaître ce langage avec une machine de Turing qui n’est pas la traduction d’un
automate. La machine suivante commence par lire le mot d’entrée de gauche à droite sur l’état 0, en
déclanchant de manière non-déterministe le test du motif abc, passant ainsi par les états 1 et 2, avant
de finir la lecture de l’entrée dans l’état 3. Atteindre l’état 3 est possible pour tous les mots de la forme
uabcv, c’est à dire ceux qui contiennent le motif recherché. Ensuite, la machine relit le mot, cette fois-ci
de droite à gauche, et cherche de manière déterministe à détecter le motif bb. La détection de ce motif
mène à l’état 6, qui se comporte comme un état « puit » : cet état n’est pas final, et aucune transition
ne permet de le quitter. Le mots contenant ce motif sont donc rejetés. À l’inverse, les mots ne contenant
pas se motif seront lus en entier par une exécution visitant les états 4 et 5 un certain nombre de fois, et
se terminant dans l’état final ok.

Paul Brunet 4/9

Calculabilité et Complexité – TD 2 –

#/#, · a/a, · b/b, ¶

i 0 1 6 5
a/a, · #/#, ·
b/b, · a/a, ¶ a/a, ¶
c/c, · c/c, ¶ c/c, ¶
a/a, · b/b, ·
b/b, · b/b, ¶
c/c, · c/c, · #/#, ¶
2 3 4 ok
#/#, ·

Exercice 5. Langages hors-contextes

Question 1. Écrire une machine de Turing acceptant les mots bien parenthèsés sur l’alphabet Σ = {a, (, )},
c’est à dire le langage décrit par la grammaire S → ε | a | SS | (S).

Solution :

a/a, ·
(/(, · a/a, ¶

#/#, · #/#, ¶ #/#, ·

i 0 2 3

)/a, ¶ (/a, ·

1 a/a, ¶

Question 2. Écrire une machine de Turing acceptant le langage {an bn | n ∈ N} .

Solution :

b/b, ·

i a/#, · 1 2 #/#, ¶
#/#, · b/b, ¶
a/a, ¶
0 a/a, · b/b, · 3

#/#, ¶ #/#, · b/#, ¶

5 4

Exercice 6.
 n
On considère le langage L := a2 n∈N .
Question 1. Proposer une machine reconnaissant L.

Solution :

A/A, · A/A, ¶
a/a, ¶ X/A, ¶
#/#, · a/A, ·
i 0 1 2 4
#/#, · A/A, ·
#/#, ¶
A/X, · a/A, ¶

5 3

Paul Brunet 5/9

Calculabilité et Complexité – TD 2 –

Question 2. Montrer que ce langage n’est pas régulier.

Solution :
n+1
On utilise le lemme de l’étoile, avec la fonction φ : n 7→ a2 . Clairement, |φ(n)| = 2n+1 > n. Considérons
n+1
une décomposion a2 = u1 u2 u3 avec u2 6= ε et |u1 u2 | ⩽ n. Je note |u2 | = k. Comme u2 6= ε et
0 n+1
|u2 | ⩽ |u1 u2 | ⩽ n, on a 0 < k ⩽ n. Or u1 (u2 ) u3 = u1 u3 = a2 −k . On remarque que comme k > 0, on
a2 n+1
− k < 2 . De plus, comme k ⩽ n < 2 , on a 2
n+1 n n+1
− k > 2n+1 − 2n = 2n . Donc 2n+1 − k est
0
strictement compris entre deux puissances de 2 successives, et donc u1 (u2 ) u3 ∈ / L.

Exercice 7. Les carrés

Les machines de Turing peuvent reconnaître plus que les langages hors-contexte. C’est le cas par exemple
⋆
du langage L := ww w ∈ {a, b} des carrés. On peut montrer, par exemple avec le lemme de la double
étoile, que ce langage n’est pas hors-contexte : il ne peut être défini à l’aide d’une grammaire hors-contexte.
⋆
Question 1. Écrire une machine de Turing reconnaissant le langage wXw, où w ∈ {a, b} .
Solution :

a/a, ·
b/b, · X/X, ·
a/a, ¶
b/b, ¶
X/X, · X/X, ¶
Xi a/#, · X1a X2a a/X, ¶
#/#, ·
#/#, ·
X0 X1
#/#, ¶ X1b X2b
X3 X2 X/#, · b/#, · b/X, ¶
X/X, ·

a/a, · X/X, ·
X/#, · b/b, ·

Question 2. Écrire une machine de Turing qui rejette les mots de longueur impaire, et pour les mots de
longueur paire insère le symbole X entre les deux moitiés du mot. Par exemple, le mot abcd est transformé
en abXcd.
Solution :

a/a, ·
b/b, ·
#/#, ¶ a/X, · #/a, ¶
#/#, · X/#, ¶ P1a
Pi P0 P1 P2
P1b
a/a, ¶ b/X, · #/b, ¶
b/b, ¶ a/a, ·
b/b, · A/a, · X/X, ¶
A/a, ¶ a/A, · B/b, ·
#/#, » B/b, ¶ X/X, ¶ b/B, · #/#, · a/a, ¶
P8 P7 P6 P5 P4 P3 b/b, ¶

Paul Brunet 6/9

Calculabilité et Complexité – TD 2 –

Question 3. Combiner les machines des deux questions précédentes pour en produire une reconnaissant L.
Solution :

a/a, ·
b/b, ·
a/X, · #/a, ¶
#/#, ¶ P1a
#/#, · X/#, ¶
Pi P0 P1 P2
b/X, · #/b, ¶
P1b
a/a, · X/X, ¶
b/b, · A/a, ·
a/A, · B/b, ·
X/X, ¶ b/B, · #/#, · a/a, ¶
P6 P5 P4 P3 b/b, ¶
a/a, ·
A/a, ¶ b/b, · X/X, ·
B/b, ¶

a/a, ¶ a/#, · X/X, · a/X, ¶

b/b, ¶ P7 #/#, · X1a X2a
#/#, · a/a, ¶
X/#, · X0 X1 b/b, ¶
X/#, · X/X, ¶
X1b X2b
b/#, · X/X, · b/X, ¶
#/#, ¶
X3 X2
a/a, · X/X, ·
b/b, ·

Question 4. Montrer que ce langage n’est pas rationnel.

Solution :
On utilise le lemme de l’étoile.
Soit un entier n. Le mot w = an ban b est un carré, et appartient donc au langage L.
En revanche pour tout découpage w = u1 u2 u3 tel que |u1 u2 | < n et u2 6= ε, on observe que le u1 u2 ne
contient que des a.
0
Par conséquent, le mot u1 (u2 ) u3 = u1 u3 est de la forme ak ban b, avec k < n. Ce mot n’est donc pas un
carré, et en temps que tel n’appartient pas à L.
Si L était régulier, d’après le lemme de l’étoile il existerait un certain entier N tel que pour tout mot w ∈ L
de longueur supérieure à N, il existe un découpage w = u1 u2 u3 avec |u1 u2 | < n et u2 6= ε, tel que pour
k
tout entier k ∈ N on aie u1 (u2 ) u3 ∈ L. On a montré plus haut une famille de mots arbitrairement longs
pour lesquels un tel découpage est impossible, ce qui prouve que L n’est pas régulier.

Paul Brunet 7/9

Calculabilité et Complexité – TD 2 –

Troisième partie – Arithmétique

Exercice 8. Calculs unaires

On se donne un alphabet {a, b}. On code l’entier n sur cet alphabet par le mot an , c’est à dire le mot
constitué de n fois la lettre a. On pourra également coder une séquence finie d’entiers hn1 , . . . , nm i par le mot
an1 ban2 · · · banm .
Question 1. Écrire une machine qui « calcule zéro », c’est à dire qu’elle prend en entrée le codage d’un entier
et produit en sortie le codage de 0.

Solution :

a/a, · a/#, ¶

#/#, · #/#, ¶ #/#, »

Zi Z0 Z1 Z2

Question 2. Écrire une machine qui incrémente son entrée d’une unité, c’est à dire qu’elle prend en entrée
le codage d’un entier n et produit en sortie le codage de n + 1.

Solution :

a/a, · a/a, ¶

#/#, · #/a, ¶ #/#, »

Ii I0 I1 I2

Question 3. Écrire une machine qui calcule l’addition, c’est à dire qu’elle prend en entrée le codage d’une
paire d’entiers hn, mi et produit en sortie le codage de n + m.

Solution :

a/a, · a/a, · a/a, ¶

#/#, · b/a, · #/#, ¶ a/#, ¶ #/#, »

Ai A0 A1 A2 A3 A4

Exercice 9. Calculs binaires

On se donne l’alphabet {0, 1, |}. On code l’entier n en binaire sur cet alphabet, avec le bit de poids fort à
droite. Par exemple, les 8 premiers entiers sont codés comme suit :

0 7→ 0 2 7→ 01 4 7→ 001 6 7→ 011
1 7→ 1 3 7→ 11 5 7→ 101 7 7→ 111.

On note [n]2 le code de l’entier n. On pourra également coder une séquence finie d’entiers hn1 , . . . , nm i par le
mot [n1 ]2 | [n2 ]2 · · · | [nm ]2 . Par exemple la paire h2, 5i est représentée par 01|101.
Question 1. Écrire une machine qui « calcule zéro », c’est à dire qu’elle prend en entrée le codage d’un entier
et produit en sortie le codage de 0.

Paul Brunet 8/9

Calculabilité et Complexité – TD 2 –

Solution :

0/0, · 1/#, ¶
1/1, · 0/#, ¶

#/#, · #/#, ¶ #/#, · #/0, ¶

Zi Z0 Z1 Z2 Z3

Question 2. Écrire une machine qui incrémente son entrée d’une unité, c’est à dire qu’elle prend en entrée
le codage d’un entier n et produit en sortie le codage de n + 1.
Solution :

0/0, ¶
1/0, · 1/1, ¶

0/1, ¶
#/#, · #/1, ¶ #/#, »
Ii I0 I1 I2

Question 3. Écrire une machine qui calcule l’addition, c’est à dire qu’elle prend en entrée le codage d’une
paire d’entiers hn, mi et produit en sortie le codage de n + m.
Question 4. Écrire une machine qui calcule la multiplication, c’est à dire qu’elle prend en entrée le codage
d’une paire d’entiers hn, mi et produit en sortie le codage de n × m.

Paul Brunet 9/9