Pourquoi le problème général de l’arrêt est-il indécidable ?
Réponse courte
Si un décideur prédisait correctement l’arrêt de tout programme sur toute entrée, on pourrait construire un programme qui fait l’inverse de sa prédiction sur sa propre description. Les deux réponses possibles le contredisent.
Comprendre
Supposer un prédicteur universel
Imaginons un programme H qui reçoit la description d’un programme P et une entrée x, puis répond correctement si P(x) termine. H est supposé terminer pour chaque couple (P, x). Un programme peut être donné comme donnée à un autre, donc on peut créer D qui consulte H sur le couple (Q, Q).
Construire la contradiction
D prend une description Q. Si H prédit que Q(Q) termine, D boucle sans fin. Si H prédit que Q(Q) ne termine pas, D s’arrête immédiatement. Exécutons maintenant D sur sa propre description. Si H répond « termine », D boucle ; si H répond « ne termine pas », D s’arrête. Dans les deux branches, H se trompe sur D(D). Le décideur supposé ne peut donc pas exister.
Portée et pièges
Cette preuve concerne le problème général pour tous les programmes et entrées. Elle n’empêche pas d’établir la terminaison d’un programme particulier : un compteur naturel qui diminue jusqu’à zéro finit, par exemple, par s’arrêter. Ne confonds pas non plus absence de décideur général et calcul lent : attendre longtemps n’est pas la preuve ; c’est la contradiction logique qui établit l’indécidabilité.
Exemples
- Si H prédit que D(D) s’arrête, D choisit la boucle infinie : la prédiction est fausse.
- Si H prédit que D(D) boucle, D choisit de terminer : cette seconde prédiction est également fausse.
Pièges fréquents
- Conclure qu’un ordinateur plus rapide peut résoudre le problème confond une limite logique avec un temps de calcul élevé.
- Étendre l’impossibilité à tout programme nie à tort les preuves de terminaison propres à des programmes particuliers.
