Exercices : calculabilité et décidabilité

Réponse B. Le problème de l’arrêt demande : « étant donné un programme P et une entrée E, est-ce que P finit par s’arrêter quand on l’exécute sur E ? ». Alan Turing a démontré en 1936 qu’il est impossible d’écrire un programme qui résout ce problème dans tous les cas.

• A est faux : déterminer un temps d’exécution polynomial relève de la complexité, pas de la terminaison ;
• C est faux : la complexité temporelle est un autre problème ;
• D est faux : les erreurs de syntaxe sont détectables par un compilateur ou un interpréteur.

Réponse B. Un problème de décision est décidable s’il existe un algorithme (une machine de Turing) qui, pour toute instance du problème, s’arrête en temps fini et donne la bonne réponse (oui ou non).

• A est faux : admettre une solution ne signifie pas qu’on peut la trouver algorithmiquement ;
• C est faux : la décidabilité concerne les algorithmes, pas les humains ;
• D est faux : la méthode de résolution n’est pas contrainte à la force brute.

Réponse C. Turing a prouvé par un raisonnement par l’absurde qu’aucun algorithme ne peut résoudre le problème de l’arrêt dans le cas général. C’est l’exemple fondateur de problème indécidable.

• A et B sont faux : le problème n’est pas décidable du tout ;
• D est faux : le problème est indécidable quel que soit le type de programme.

Réponse B. Un problème est dans NP (nondeterministic polynomial) si, étant donnée une solution candidate, on peut vérifier en temps polynomial qu’elle est correcte. Cela ne signifie pas que trouver la solution est nécessairement long.

• A est faux : les problèmes NP sont résolubles (en temps éventuellement exponentiel) ;
• C est faux : certains problèmes NP sont aussi dans P (résolubles en temps polynomial) ;
• D est faux : les problèmes NP ont des solutions.

Réponse B. La question P = NP demande si tout problème dont la solution est vérifiable en temps polynomial (classe NP) est aussi résoluble en temps polynomial (classe P). C’est l’un des plus grands problèmes ouverts en informatique et en mathématiques.

• A est faux : certains problèmes sont indécidables, indépendamment de P vs NP ;
• C est faux : les machines de Turing sont un modèle théorique équivalent en puissance aux ordinateurs ;
• D est faux : le problème de l’arrêt est indécidable, ce qui est un résultat établi.

1. Un programme est stocké sous forme de texte (son code-source), qui est une suite de caractères. Cette suite de caractères peut être lue, transmise ou analysée par un autre programme, exactement comme n’importe quelle autre donnée. Par exemple, quand on exécute python3 test.py, le programme python3 reçoit en paramètre le fichier test.py qui contient le code-source d’un autre programme.

2. L’interpréteur Python est un programme qui prend en paramètre le code-source d’un programme Python. De même, un compilateur C prend en paramètre un fichier .c et produit un exécutable. Autre exemple : un débogueur est un programme qui analyse l’exécution d’un autre programme.

3. Un quine est un programme qui affiche son propre code-source sans lire aucun fichier. La ligne a='a=%r;print(a%%a)';print(a%a) affiche exactement a='a=%r;print(a%%a)';print(a%a), c’est-à-dire elle-même.

1. countdown(5) affiche 5, 4, 3, 2, 1, puis « fini ». Il s’arrête car n atteint 0 après cinq itérations.

2. countdown(-3) ne s’arrête jamais (boucle infinie). La condition n != 0 est toujours vraie car n vaut successivement −3, −4, −5, … et ne sera jamais égal à 0.

3. countdown(2.5) ne s’arrête jamais (boucle infinie). Les valeurs successives de n sont 2.5, 1.5, 0.5, −0.5, −1.5, … La valeur 0 n’est jamais atteinte.

4. Version corrigée :

   def countdown(n):
       while n > 0:         # remplacer != par >
           print(int(n))
           n = n - 1
       print("fini")
   

   Avec n > 0, la boucle s’arrête dès que n devient négatif ou nul, quel que soit le type de n.

1. Si halt(sym, sym) renvoie True, cela signifie que sym(sym) devrait s’arrêter. Or, dans ce cas, sym entre dans la boucle infinie while True et ne s’arrête jamais. Contradiction.

2. Si halt(sym, sym) renvoie False, cela signifie que sym(sym) ne devrait pas s’arrêter. Or, dans ce cas, sym exécute return 0 et s’arrête. Contradiction.

3. Dans les deux cas, la prédiction de halt est fausse. Donc la fonction halt ne peut pas exister : le problème de l’arrêt est indécidable.

La preuve procède par l’absurde : on suppose que halt existe, on construit sym qui contredit systématiquement la prédiction, et on arrive à une contradiction dans tous les cas.

1. Décidable. Il existe des algorithmes de test de primalité qui terminent toujours (divisions successives, Miller-Rabin, AKS).

2. Indécidable. C’est une question sémantique (sur le comportement) d’un programme arbitraire. Par le théorème de Rice, toute question sémantique non triviale sur un programme est indécidable.

3. Décidable. La recherche dichotomique termine toujours et donne une réponse en \(\mathcal{O}(\log n)\).

4. Indécidable. C’est le problème de l’équivalence de programmes, auquel se réduit le problème de l’arrêt (théorème de Rice).

5. Décidable. Il suffit de tester si n % 2 == 0. L’algorithme termine toujours.

6. Décidable. C’est une question syntaxique (sur la forme du code, pas sur son comportement). Il suffit de chercher le mot-clé while dans le code-source. Le théorème de Rice ne s’applique qu’aux questions sémantiques.

1. P. Le tri fusion résout ce problème en \(\mathcal{O}(n \log n)\), qui est polynomial.

2. NP-complet. Aucun algorithme polynomial n’est connu. En revanche, si on propose un cycle, on peut vérifier en temps polynomial qu’il est hamiltonien (il suffit de vérifier que chaque sommet apparaît exactement une fois et que les arêtes existent).

3. P. La recherche dichotomique résout ce problème en \(\mathcal{O}(\log n)\).

4. NP-complet. La version décision du sac à dos (« peut-on atteindre exactement la valeur \(V\) sans dépasser la capacité ? ») est NP-complète. Vérifier qu’un ensemble d’objets satisfait les contraintes est polynomial, mais trouver cet ensemble ne l’est pas (en l’état des connaissances).

5. P. La multiplication de matrices se fait en \(\mathcal{O}(n^3)\) (algorithme classique) ou mieux avec l’algorithme de Strassen en \(\mathcal{O}(n^{2.81})\). Ces complexités sont polynomiales.

1. Faux. Le problème de l’arrêt ne dit pas que certains programmes ne s’arrêtent pas (cela, on le sait déjà avec les boucles infinies). Il dit qu’aucun algorithme ne peut prédire de manière générale si un programme donné va s’arrêter ou non.

2. Faux. Tout problème de P est aussi dans NP, et les problèmes de P ne sont pas considérés comme difficiles. NP contient des problèmes faciles (P) et des problèmes potentiellement difficiles (NP-complets).

3. Vrai. Si un problème peut être résolu en temps polynomial, alors sa solution peut aussi être vérifiée en temps polynomial. Donc P ⊂ NP.

4. Faux. NP signifie « Non-déterministe Polynomial », c’est-à-dire résolu en temps polynomial par une machine de Turing non déterministe.

5. Vrai. La sécurité du RSA repose sur le fait que la factorisation de grands nombres est considérée comme difficile (pas dans P). Si P = NP, la factorisation aurait un algorithme polynomial, ce qui rendrait le RSA vulnérable.

6. Faux. Le théorème de Rice concerne les questions sémantiques (sur le comportement) et non triviales. Les questions syntaxiques (sur la forme du code) restent décidables. Par exemple, « ce programme contient-il une boucle for ? » est décidable.

1. Soit p un programme et x une entrée. On construit le programme q suivant :

   def q(n):
       p(x)       # on exécute p(x) ; si p(x) ne s'arrête pas, q non plus
       return 42   # atteint seulement si p(x) s'arrête
   

   Si p(x) s’arrête, alors q(0) exécute p(x) puis renvoie 42. Donc test42(q) renvoie True.

   Si p(x) ne s’arrête pas, alors q(0) boucle indéfiniment et ne renvoie jamais 42. Donc test42(q) renvoie False.

   On a donc : test42(q) renvoie True si et seulement si p(x) s’arrête. Autrement dit, test42 permet de résoudre le problème de l’arrêt.

2. Or le problème de l’arrêt est indécidable. Si test42 existait, on pourrait résoudre le problème de l’arrêt, ce qui est impossible. Donc test42 ne peut pas exister : le problème « prog(0) renvoie-t-il 42 ? » est indécidable.

C’est un exemple de réduction : on a montré que résoudre le nouveau problème permettrait de résoudre un problème déjà connu comme indécidable.

1. Vérifier une grille de sudoku remplie consiste à contrôler que chaque ligne, chaque colonne et chaque bloc 3×3 contient les chiffres de 1 à 9 sans répétition. Il y a 27 groupes de 9 cases à vérifier, soit un nombre fixe de vérifications : la complexité est \(\mathcal{O}(1)\) pour une grille 9×9 (ou \(\mathcal{O}(n^2)\) pour une grille \(n \times n\), ce qui reste polynomial).

2. Essayer toutes les grilles possibles reviendrait à tester jusqu’à \(9^{81} \approx 2 \times 10^{77}\) configurations (en réalité moins avec les contraintes, mais c’est un nombre astronomique). C’est une approche exponentielle, inenvisageable en pratique.

3. Oui, le tri est aussi dans NP. Puisque P ⊂ NP, tout problème résolu en temps polynomial est aussi vérifiable en temps polynomial. Concrètement, vérifier qu’une liste est triée se fait en \(\mathcal{O}(n)\) (parcourir la liste et vérifier que chaque élément est inférieur ou égal au suivant).