Université de Garoua Année académique 2024/2025
Faculté des sciences Master / Semestre 1
Département de Mathématiques et Informatique Parcours Informatique
TD Calculabilité et complexité des algorithmes
I. LES MACHINES DE TURING
1. Décrire des machines de Turing qui acceptent les langages suivants :
anbncn
Les mots de la forme wwn construits sur l’alphabet {a, b}
Les mots de l’alphabet {a, b} dont la longueur est une puissance de 2.
2. Construire des machines de Turing qui décident les langages décrits en 1).
3. Construire une machine de Turing dont l’alphabet d’entrée est {0, 1} et qui
calcule la représentation unaire de son mot d’entrée (une séquence de 1 dont la
longueur est égale à la valeur du mot d’entrée).
4. Construire une machine de Turing qui calcule la somme de deux nombres
représentés en notation binaire.
5. Soit M = ( K , , , , q0 , F ) la machine de Turing d'état initial q0, avec
acceptation par état final (unique état acceptant q7), d'alphabet = a, b,
d'alphabet de ruban = a, b, X , Y , # avec la fonction de transition donné
par le tableau ci-dessous :
a b X Y #
q0 (q1, #, D)
q1 (q2, X, D)
q2 (q3, X, D) (q6, Y, D)
q3 (q3, a, D) (q4, Y, D) (q3, Y, D)
q4 (q5, Y, G)
q5 (q5, a, G) (q2, X, D) (q5, Y, G)
q6 (q6, Y, D) (q7, #, --)
q7
a) Dessiner l’automate.
b) Le mot a3b4 est-il accepté par M ? Donner les configurations successives.
c) Donner les configurations successives, dire si les mots a3b3 et a3b5 sont
acceptés par M.
d) Quel langage est reconnu par cette machine de Turing ? On justifiera.
e) Modifier cette machine pour reconnaître le langage {anb2n, n1}.
Justifier.
6. Soit le langage w a, b / w a = w b
*
a) Donner la description d’une machine de Turing acceptant le langage.
b) Construire la machine de Turing.
Page 1
Université de Garoua Année académique 2024/2025
Faculté des sciences Master / Semestre 1
Département de Mathématiques et Informatique Parcours Informatique
TD Calculabilité et complexité des algorithmes
7. Soit M = (Q, , , , q0 , B, qF ) la machine de Turing où Q = ( q0 , qa , qb );
= a,b; = a, b, B; δ est donnée par (q0 , a ) (qa , a, R ) ;
(q0 , b) (qb , b, R ); (q , a ) (q , a, R ) ;
a a
(qa , b) (qa , b, R ) ;
(qb , a ) (qb , a, R ); (q , b) (q , b, R );
b b
(qa , B ) (qF , a, R ) ;
(qb , B ) (qF , b, R ) .
a. Dessiner cette machine sous la forme d’un automate.
b. Donner la configuration à la fin de l’exécution de M sur le mot d’entrée
abab ?
c. Quelle fonction est calculée par cette machine ?
8. Soit la machine de Turing sur l’alphabet {a, b, ♡} donnée par le diagramme de
transitions suivant. Les x représentent soit a, soit b, soit ♡, c’est-à-dire que
chaque transition étiquetée par x correspond en fait à trois transitions similaires,
l’une étiquetée par a la deuxième par b et la dernière par ♡.
a. Simuler l’exécution de cette machine sur l’entrée aab (donner la suite des
configurations).
b. A votre avis, quelle est la fonction calculée par cette machine ?
Page 2
Université de Garoua Année académique 2024/2025
Faculté des sciences Master / Semestre 1
Département de Mathématiques et Informatique Parcours Informatique
TD Calculabilité et complexité des algorithmes
II. DECIDABILITE
1. Supposons que A ⊆ B ⊆ N.
Si B est décidable, peut-on conclure que A est décidable ?
Si A est décidable, peut-on conclure que B est décidable ?
2. Soit f : IN → IN totale calculable. Montrer que l’image f (IN) (c’est-à-
dire f (i) : i INest semi-décidable.
3. Soit f : IN → IN totale calculable et strictement croissante. Montrer que
l’image f (IN) (c’est-à-dire f (i) : i IN est décidable
III. LES FONCTIONS RECURSIVES
1. Démontrer les lemmes et théorèmes suivants :
Lemme 1 : Il existe une représentation effective des nombres naturels par
de chaines de caractères.
Lemme 2 : Il existe une représentation effective des chaines de caractères
par les naturels.
Théorème 1 : Toute fonction -récursive est calculable par une machine
de Turing.
Théorème 2 : Toute fonction calculable par une machine de Turing est -
récursive.
2. Montrer que le prédicat divise(m, n), qui est vrai si m divise n, est primitive
récursif.
3. La fonction SommeDiviseurs est définie de la facon suivante : si n IN , alors
SommeDiviseurs(n) renvoie la somme des diviseurs entiers positifs de n (n non
compris). Par exemple SommeDiviseurs(6) = 1 + 2 + 3 = 6. Montrez que
SommeDiviseurs est primitive récursive. On pourra définir une fonction
auxiliaire avec un argument de plus. On pourra également utiliser la
fonction modulo(n, m) n[m] (ou n mod m) supposée primitive
récursive, et une définition par cas ite(x, y, b) = if (b > 0) then x else y
supposée aussi primitive récursive.
4. Soit g une fonction récursive primitive. Soit f la fonction définie par f(0, x) =
g(x) et f(n + 1, x) = f(n, f(n, x)). Montrez que f est récursive primitive. On
commencera par prouver proprement que f : (n, x) g2n (x), et on
pourra utiliser sans preuve le fait que la fonction 2_puis : n 2n, est
récursive primitive.
Page 3
Université de Garoua Année académique 2024/2025
Faculté des sciences Master / Semestre 1
Département de Mathématiques et Informatique Parcours Informatique
TD Calculabilité et complexité des algorithmes
5. Montrer que la fonction max n : IN n → IN qui à (x , x ,...,x )
1 2 n
associe le
maximum des n entiers x1 , x2 ,...,x n est primitive récursive. On peut considérer
acquis que le prédicat est primitif récursif.
6. Montrer que la fonction pgcd(m, n), donnant le plus grand commun diviseur de
m et n est primitive récursif.
7. Montrer qu'une fonction totale f : N → N est calculable si et seulement si son
graphe : G = {(x, f (x)) | x appartient à N} est décidable.
IV. LA NON-CALCULABILITE
1. Les langages réguliers sont-ils décidables ? Justifier. Qu’en est-il des langages
hors contextes ?
2. Démonter que le problème de déterminer si deux grammaires G1 et G2 génèrent
le même langage est indécidable.
3. Démontrer que déterminer si deux machines de Turing acceptent le même
langage est un problème indécidable.
4. Démontrer que déterminer si l’intersection des langages acceptés par deux
machines de Turing est le langage vide est un problème indécidable.
5. Démontrer que déterminer l’égalité de deux langages hors-contexte est un
problème indécidable.
6. Montrez, par réduction à partir du problème de l’arrêt, que le problème suivant
est indécidable :
Entrée : une machine de Turing M qui s’arrête sur toutes les données.
Sortie : L(M) est-il infini ?
V. LA COMPLEXITE
1. Est-ce que les langages réguliers sont dans la classe P ? Justifier Qu’en est-il
des langages hors-contexte ?
2. Donner des algorithmes déterministes résolvant chacun des problèmes
suivants : Le problème du Circuit Hamiltonien ; le problème SAT ; le problème
du Voyageur de Commerce. Estimer la complexité de ces algorithmes.
3. Démontrer que, pour tout k4, le problème k-SAT (satisfaisabilité d’un
ensemble de clauses de k éléments) est NP-complet.
4. Le problème du chemin le plus long (longest path, abbréviation LP) est décrit
comme suit. Les données sont un graphe G=(V, E) et un entier J V . La
question à résoudre est de déterminer si le graphe contient un chemin simple (ne
comportant pas deux fois le même sommet) contenant au moins J arcs.
Démontrer que LP est NP-complet.
Page 4
