Un cap pour ce chapitre
Ce que vous saurez faire
- Distinguer calculabilité et efficacité.
- Définir une décision algorithmique totale.
- Expliquer la contradiction du problème de l’arrêt.
Décider exige une réponse qui arrive
Un problème de décision demande une réponse oui ou non pour chaque entrée autorisée. Un algorithme qui décide ce problème doit donner la bonne réponse et terminer pour toutes ces entrées. Un programme qui répond correctement lorsqu’il termine, mais reste parfois bloqué indéfiniment, ne constitue pas un décideur total.
Par exemple, décider si un entier naturel est pair est possible : calculer son reste modulo deux suffit. Chercher un élément dans une liste finie est également décidable. La quantité de travail peut varier avec la taille de l’entrée. La décidabilité ne promet donc ni une réponse instantanée ni une utilisation raisonnable des ressources.
Changer de langage ne supprime pas une limite générale
Les langages généralistes étudiés peuvent exprimer les mêmes calculs au sens théorique, lorsqu’on idéalise la mémoire disponible. Un algorithme peut alors être traduit d’un langage à un autre. Les performances, les bibliothèques et le confort d’écriture changent, mais une impossibilité de calculabilité ne disparaît pas simplement en passant de Python à un autre langage généraliste.
Cette affirmation porte sur une notion abstraite de calcul, pas sur toutes les contraintes des machines réelles. Une machine possède une mémoire finie, des limites de temps et des interfaces particulières. Il faut distinguer le modèle théorique utilisé pour raisonner des conditions pratiques d’une exécution.
Supposer un détecteur universel de terminaison
Imaginons un programme H qui prend le code d’un programme P et une entrée x. H termine toujours et répond vrai exactement lorsque P termine sur x. Nous allons montrer qu’un tel outil général ne peut pas exister. Le raisonnement suppose H parfait, pas seulement très performant sur beaucoup de cas.
Construisons D qui reçoit le code d’un programme P. D demande à H si P termine lorsqu’on lui donne son propre code en entrée. Si H répond oui, D se met volontairement à boucler sans fin. Si H répond non, D termine immédiatement. Cette construction est possible sous l’hypothèse que H existe : un programme peut manipuler un autre programme comme une donnée.
Le quantificateur « tous » est essentiel. H doit accepter aussi les programmes qui lisent du code, ceux qui interrogent H et celui construit pour contrarier sa réponse. Exclure après coup ce programme particulier changerait la promesse de départ et ne sauverait pas un décideur universel.
Appliquer D à son propre code
Demandons maintenant ce que fait D lorsqu’il reçoit son propre code. Si H prédit que D termine sur D, la règle de construction fait boucler D : la prédiction est fausse. Si H prédit que D ne termine pas sur D, la règle fait terminer D immédiatement : la prédiction est encore fausse. Les deux réponses possibles conduisent à une contradiction.
Il n’existe donc aucun décideur universel de l’arrêt pour tous les programmes et toutes les entrées du modèle. Cela n’empêche pas de prouver la terminaison d’un programme particulier, de reconnaître certaines boucles infinies ou de construire des analyseurs utiles. L’impossibilité concerne une solution parfaite et générale, pas toute forme d’analyse.
Exemple suivi : une simulation limitée décide une autre question
Demandons si un programme s’arrête en au plus cent étapes. On peut le simuler pendant cent étapes, répondre oui si l’arrêt est observé, puis non sinon. Cet algorithme termine : la limite borne le travail. La question est cependant différente de « s’arrêtera-t-il un jour ? ». Un programme qui termine à l’étape cent une donne non à la première question et oui à la seconde.
Laisser simplement tourner un programme permet de constater son arrêt lorsqu’il survient. Si rien ne se passe, après une minute, un jour ou une année, on ne sait pas encore distinguer une exécution infinie d’une exécution finie plus longue. Aucun délai arbitraire ne remplace une preuve générale. Cette distinction explique pourquoi une commande d’interruption protège une session de travail sans résoudre le problème théorique de l’arrêt.
Exemple suivi : vérifier les deux lignes de la contradiction
Écrivez un tableau avec la prédiction de H et le comportement imposé à D sur son propre code. Première ligne : H répond « termine » ; D boucle ; la prédiction est fausse. Seconde ligne : H répond « ne termine pas » ; D termine ; la prédiction est encore fausse. Il n’existe aucune troisième réponse autorisée puisque H était supposé décider par oui ou non et terminer dans tous les cas.
La contradiction ne vient pas d’un programme simplement « difficile à comprendre », ni d’un manque de puissance de la machine. Elle vient de l’incompatibilité entre la promesse de H et une construction que cette promesse permet d’exprimer. Un outil utile peut renoncer à une des exigences : analyser seulement une famille de programmes, répondre inconnu, ou fournir des avertissements qui demandent une vérification humaine. Ces choix n’affirment pas l’existence du H impossible.
| Prédiction de H sur D(D) | Comportement imposé à D(D) | Conclusion |
|---|---|---|
| Termine | Boucle sans fin | La prédiction est fausse |
| Ne termine pas | Termine immédiatement | La prédiction est fausse |
À vous de faire varier les choses
Limite théorique ou difficulté pratique ?
Classez chaque affirmation. Les retours précisent la portée de ce qu’on peut conclure.
Lire les associations expliquées
- Tester si un entier naturel est pair. : Décision possible
- Le reste modulo deux donne une réponse et termine.
- Chercher une valeur dans une liste finie. : Décision possible
- Un parcours fini suffit.
- Un calcul connu demande plus de mémoire que la machine disponible. : Difficulté de ressources
- La machine limite cette exécution ; cela ne prouve pas une indécidabilité.
- Un algorithme correct prend des millions d’années sur une entrée. : Difficulté de ressources
- Sa durée pratique n’annule pas son existence.
- Décider toujours correctement l’arrêt de tout programme sur toute entrée. : Promesse générale impossible
- C’est exactement la promesse contredite par le raisonnement diagonal.
- Prouver qu’une boucle termine : tant que n est strictement positif, elle remplace n par n moins un ; n est initialement entier naturel. : Décision possible
- Un variant établit ce cas particulier.
- Remplacer Python par un langage généraliste pour rendre décidable le problème général de l’arrêt. : Promesse générale impossible
- La limite de calculabilité ne disparaît pas avec cette traduction.
- Décider si un programme s’arrête durant les cent premières étapes en simulant exactement cette limite. : Décision possible
- Le compteur borne la simulation. La question porte sur un délai fini et ne décide pas un arrêt éventuel au-delà.
- Une recherche exhaustive finit théoriquement, mais sa table dépasse la mémoire disponible. : Difficulté de ressources
- La contrainte concerne les ressources de cette machine. Elle ne prouve pas que le problème n’admet aucun algorithme.
- Un analyseur, total et sans réponse inconnu, promet une décision exacte de terminaison pour tous les codes, y compris le sien. : Promesse générale impossible
- Les conditions du détecteur H sont réunies. Le programme diagonal construit une contradiction à partir de sa propre réponse.
Une impossibilité générale est compatible avec de nombreuses analyses particulières utiles.
De la compréhension à l’autonomie
À vous de résoudre
Cherchez d’abord par vous-même. Vérifiez les résultats demandés, utilisez les indices si nécessaire, puis comparez votre méthode à la correction.
Classer une difficulté
Un algorithme termine toujours mais demanderait mille ans sur une entrée volumineuse. Cela prouve-t-il que le problème est indécidable ?
Indice 1
La définition exige-t-elle un délai pratique ?
Indice 2
Séparez existence d’un algorithme et coût de son exécution.
Comprendre la correction
Non. Si l’algorithme fournit une réponse correcte et termine sur toutes les entrées, le problème est décidable. Mille ans rendent son emploi impraticable dans cette situation, mais ne constituent pas une impossibilité algorithmique théorique.
Traiter un cas particulier
La boucle while n > 0: n = n - 1, avec n initialement entier naturel, termine-t-elle ? Pourquoi cela ne contredit-il pas le résultat général sur le problème de l’arrêt ?
Indice 1
La quantité n est entière et décroît.
Indice 2
Le théorème concerne tous les programmes sans exception.
Comprendre la correction
Elle termine : n décroît d’une unité et ne peut rester positif indéfiniment. Nous avons prouvé un cas particulier grâce à une propriété précise. L’indécidabilité de l’arrêt n’interdit pas de telles preuves ; elle interdit un outil total et correct pour l’ensemble de tous les cas.
Compléter la contradiction
H prédit que D appliqué à lui-même termine. Que fait alors D par construction, et quelle contradiction obtient-on ?
Indice 1
D réalise volontairement le comportement opposé à la prédiction.
Indice 2
Comparez le comportement à la réponse supposée correcte.
Comprendre la correction
D se met à boucler indéfiniment, puisque H a répondu oui. H a donc annoncé la terminaison d’une exécution qui ne termine pas. Cela contredit l’hypothèse selon laquelle H est toujours correct. L’autre réponse conduit symétriquement à une contradiction.
Évaluer une promesse d’outil
Un outil repère correctement beaucoup de boucles infinies mais indique parfois « inconnu ». Est-il nécessairement impossible ?
Indice 1
Est-ce le décideur universel supposé dans la preuve ?
Indice 2
La réponse inconnu abandonne une exigence.
Comprendre la correction
Non. Un analyseur partiel peut être utile et correct dans les cas qu’il sait traiter. En répondant parfois inconnu, il ne prétend pas décider tous les programmes. Il ne satisfait donc pas les hypothèses impossibles réunies dans H.
Problème : analyser un délai maximal
Un outil simule tout programme pendant 1 000 étapes. Il répond « arrêt observé » ou « aucun arrêt observé ». Donne-t-il une information correcte ? Décide-t-il l’arrêt sans limite ? Construisez un programme qui termine mais n’est pas observé à temps.
Indice 1
Les mots « observé » limitent la portée de la réponse.
Indice 2
Une boucle de 1 001 itérations suffit si chaque itération demande au moins une étape.
Comprendre la correction
L’outil peut décrire correctement son observation bornée. Il ne décide pas l’arrêt général : une boucle de 1 001 itérations puis un retour termine, mais pas dans les 1 000 premières étapes de ce modèle. Remplacer « aucun arrêt observé » par « ne terminera jamais » produirait une conclusion injustifiée. Le délai est un paramètre d’expérimentation, pas un certificat de non-terminaison.
Problème : réparer une preuve incomplète
Une rédaction suppose H universel et décrit uniquement le cas où H annonce la terminaison de D(D). Complétez l’autre cas. Expliquez pourquoi H ne peut pas répondre « inconnu » dans cette preuve, puis pourquoi un outil réel qui le fait n’est pas réfuté de la même manière.
Indice 1
D inverse les deux réponses possibles.
Indice 2
Relisez les exigences de la fonction hypothétique H.
Comprendre la correction
Si H annonce la non-terminaison de D(D), la règle de D impose un arrêt immédiat ; H se trompe encore. La promesse supposée n’autorise que deux réponses correctes sur chaque entrée : inconnu l’abandonnerait. Un analyseur réel autorisant inconnu peut donc exister ; il fournit un service partiel et ne prétend pas remplir le contrat universel impossible.
Problème : choisir une conclusion adaptée
Un programme de recherche dans une liste finie prend trop de temps ; une boucle while n > 0: n = n - 1 part d’un entier naturel ; une société promet un outil parfait décidant l’arrêt de tout code. Pour chacun, dites ce qui peut être conclu et quelle justification convient. Une réécriture dans un autre langage généraliste change-t-elle la troisième conclusion ?
Indice 1
Le premier problème possède déjà un algorithme fini.
Indice 2
Le second possède un variant naturel qui décroît.
Comprendre la correction
La recherche finie est décidable mais peut être coûteuse ; on étudie son algorithme ou ses données. La boucle se prouve terminante grâce à la décroissance vers zéro. La promesse générale contredit l’argument diagonal. Une traduction vers un langage généraliste de même puissance de calcul ne supprime pas cette limite ; elle peut modifier l’efficacité ou le confort, pas la décidabilité.
Les erreurs qui méritent un détour
- Conclure que toute terminaison est impossible à démontrer.
- La limite porte sur un décideur universel, pas sur une preuve particulière.
- Confondre mémoire insuffisante et indécidabilité.
- Les ressources pratiques et l’existence théorique d’un algorithme sont deux questions.
La fiche à garder
L’essentiel à retenir
- Un décideur doit terminer et répondre correctement sur toutes les entrées autorisées.
- La calculabilité théorique ne dépend pas du choix d’un langage généraliste équivalent.
- Le problème général de l’arrêt est indécidable par un raisonnement de contradiction.
Cette notion au bac
Retrouvez ces idées dans un sujet complet, avec des indices, une correction expliquée et des ateliers.
Le prochain pas
Retrouver le catalogue de Terminale
Ce chapitre s’appuie sur le programme officiel de Terminale (PDF, nouvel onglet). Les explications et exercices sont proposés pour l’apprentissage.