Calculabilité et décidabilité : exercices corrigés de Terminale NSI

Pour la question 1, on écrit def est_pair(n): return n % 2 == 0. Cette fonction effectue une seule opération et se termine toujours.

Pour la question 2, on écrit def multiple_de_7(n): return n % 7 == 0. Là encore, un calcul unique suffit, sans boucle.

Pour la question 3, on écrit une boucle for i in range(len(t) - 1) qui renvoie False dès que t[i] > t[i+1], et True à la sortie de la boucle. La liste est finie, donc la boucle fait au plus len(t) - 1 tours.

Chaque fonction termine pour toute entrée et renvoie la bonne réponse. D'après la définition, chaque prédicat est calculable, donc chaque problème est décidable ¹.

On repère la condition : est_pair(n) renvoie True quand le reste de la division de n par 2 vaut 0.

Parmi les entiers de 1 à 20, les pairs sont 2, 4, 6, 8, 10, 12, 14, 16, 18 et 20.

On les compte : il y en a 10.

On écrit def est_compose(n): return not est_premier(n). La fonction appelle est_premier puis inverse la réponse.

est_premier(n) termine toujours par hypothèse, et la négation est une opération immédiate : est_compose termine donc toujours aussi. On retrouve le fait que le complémentaire d'un ensemble décidable est décidable ³.

De 2 à 30, il y a 29 entiers.

Parmi eux, 10 sont premiers : 2, 3, 5, 7, 11, 13, 17, 19, 23 et 29.

Le nombre d'entiers non premiers est donc 29 − 10 = 19.

Si n est pair, la suite n, n-2, n-4, … atteint exactement 0, donc la boucle s'arrête.

Si n est impair, la suite passe par 1, puis −1, −3, … : elle saute par-dessus 0 sans jamais le valoir. La boucle ne s'arrête jamais.

Entre 0 et 20, les entiers pairs sont 0, 2, 4, …, 20, soit 11 valeurs. Onze calculs s'arrêtent.

Pour la question 3, la réponse est non. On peut écrire def s_arrete(n): return n % 2 == 0, qui termine toujours et donne la bonne réponse pour ce programme. Le problème de l'arrêt de descente est donc décidable.

La fonction de l'élève arrête toujours sa simulation au bout de 1 000 000 d'étapes au plus. Elle termine donc pour toute entrée.

Elle ne résout pas le problème de l'arrêt, car la réponse False signifie seulement « pas arrêté dans le délai fixé ». Un programme qui s'arrête après 2 000 000 d'étapes obtient la mauvaise réponse False.

Pour la question 3, les valeurs de n sont : 50, 25, 12, 6, 3, 1.

La boucle s'arrête quand n vaut 1. Il faut 5 divisions pour passer de 50 à 1, donc le calcul de f(50) effectue 5 tours de boucle.

Si arret(p, p) vaut True, paradoxe(p) entre dans une boucle infinie. Si arret(p, p) vaut False, paradoxe(p) renvoie immédiatement « fini » : le calcul s'arrête.

Dans paradoxe(paradoxe), on prend p = paradoxe. Premier cas : si arret(paradoxe, paradoxe) vaut True, la fonction prédit que le calcul s'arrête, mais paradoxe(paradoxe) boucle alors indéfiniment. Contradiction.

Second cas : si arret(paradoxe, paradoxe) vaut False, la fonction prédit que le calcul ne s'arrête pas, mais paradoxe(paradoxe) renvoie « fini » et s'arrête. Nouvelle contradiction.

Les deux cas sont impossibles. L'hypothèse de départ était donc fausse : aucune fonction arret ne peut exister.

On écrit def boucle_infinie(p, x): return not arret(p, x).

Cette fonction termine toujours si arret termine toujours : le problème « boucle indéfiniment » serait décidable, ce qui est cohérent avec le fait que le complémentaire d'un ensemble décidable est décidable ³.

Réciproquement, si on disposait d'un décideur boucle_infinie, alors not boucle_infinie(p, x) serait un décideur pour l'arrêt.

Or un tel décideur n'existe pas, puisque le problème de l'arrêt est indécidable ³. Il n'existe donc pas non plus de décideur pour « le calcul boucle indéfiniment ».

Question 1 : elle porte sur le texte du programme, pas sur son comportement. On compte les lignes, c'est un calcul qui termine toujours. Elle est décidable et ne relève pas du théorème de Rice, qui concerne les questions dépendant seulement du résultat du calcul ³.

Question 3 : même raison. On cherche le mot while dans le texte, ce qui termine toujours. Elle est décidable.

Question 2 : elle dépend uniquement du résultat produit par le programme. Elle n'est pas triviale, car certains programmes renvoient toujours 0 et d'autres non. D'après le théorème de Rice, elle est indécidable ³.

Question 4 : elle porte sur la terminaison du calcul, une propriété de comportement. Elle est elle aussi indécidable d'après le théorème de Rice ³, ce qui rejoint le problème de l'arrêt.

Le logiciel décrit décide le problème de l'arrêt pour tous les programmes d'un langage usuel. Or il n'existe pas de programme capable de tester n'importe quel programme d'un langage suffisamment puissant afin de conclure dans tous les cas s'il s'arrête ³. La promesse est donc impossible à tenir.

Cela n'interdit pas les outils d'analyse partielle. Un outil peut traiter correctement certaines familles de programmes, par exemple ceux qui n'ont que des boucles for sur des listes finies, qui terminent toujours.

Une version réaliste peut répondre « s'arrête », « ne s'arrête pas » ou « je ne sais pas ». Elle reste fiable quand elle tranche, et elle avoue son ignorance sinon.

Le nombre de mots à tester est fini, donc la recherche exhaustive termine toujours. Le problème est décidable.

Chaque lettre a 26 choix, indépendamment des autres : il y a $26^6 = 308\,915\,776$ mots de passe possibles.

À $10^6$ tests par seconde, le temps maximal est $\dfrac{308\,915\,776}{10^6} \approx 309$ secondes, soit environ 5 minutes. C'est raisonnable.

Pour 20 lettres, il y aurait $26^{20}$ mots, un nombre qui dépasse $10^{28}$. Le même calcul donne un temps de plus de $10^{22}$ secondes, très supérieur à toute durée humaine : la recherche est décidable mais impraticable.