problème de l'arrêt

Imaginez un outil auquel on donne un programme et ses données. L'outil doit annoncer si le calcul finira ou continuera sans fin, avant d'attendre lui-même indéfiniment. Pour certains programmes, la réponse est visible. Le problème de l'arrêt demande s'il existe une recette qui réussit à tous les coups.

Turing a prouvé que cette recette universelle n'existe pas. Cela n'empêche pas d'étudier un programme particulier ; cela interdit un algorithme unique qui donnerait toujours le bon verdict pour n'importe quel programme et n'importe quelle entrée.

Le problème de l'arrêt est un problème de décision en théorie de la calculabilité. Ses données sont une machine de Turing M, qui représente un programme quelconque, et un mot w, qui représente son entrée. La question est de savoir si l'exécution de M sur w atteint un état d'arrêt après un nombre fini d'étapes.

Supposons qu'un algorithme H renvoie 1 lorsqu'il prédit l'arrêt et 0 lorsqu'il prédit une exécution infinie :Résoudre le problème exigerait que H termine et donne la bonne réponse pour toute paire formée d'une machine M et d'une entrée w.

Alan Turing a démontré en 1936 qu'un tel algorithme général n'existe pas. Le problème est donc indécidable. La preuve construit, par diagonalisation, un programme dont le comportement contredit le verdict de H lorsqu'il est appliqué à sa propre description. Cet argument est analogue, dans son principe, à la diagonale de Cantor. Cette impossibilité porte sur toutes les machines et toutes les entrées à la fois, pas sur la possibilité de conclure dans certains cas particuliers.

Supposons, pour obtenir une contradiction, qu'un décideur H réponde toujours correctement. Construisons un programme D qui reçoit la description d'un programme P et consulte H sur P exécuté avec sa propre description.

Données :
H termine pour toute paire programme-entrée ;
D boucle si H annonce que P s'arrête sur P ;
D s'arrête si H annonce que P boucle sur P.

1. Donnons à D sa propre description : D exécute alors H sur la paire (D, D).
2. Si H annonce « arrêt », D suit sa règle et boucle : l'annonce est fausse.
3. Si H annonce « boucle », D s'arrête : l'annonce est encore fausse.
4. Les deux verdicts possibles contredisent donc l'hypothèse que H répond toujours correctement.

Le contrôle consiste à refaire les deux branches : chaque prédiction impose à D le comportement opposé. Il ne reste aucun verdict cohérent pour H(D, D), donc le décideur universel supposé ne peut pas exister.

Pour un programme précis, une preuve peut montrer qu'une boucle progresse vers une condition d'arrêt. Quand cet invariant et cette progression sont établis, ils donnent un verdict pour ce cas sans prétendre traiter tous les programmes.

Un analyseur peut aussi reconnaître certaines boucles sans fin ou garantir l'arrêt dans une famille restreinte de programmes. Si ses hypothèses ne sont pas remplies, il doit conserver un verdict indéterminé plutôt que promettre une décision universelle.

Interrompre une exécution après un délai est utile pour protéger un système. Ce délai ne prouve toutefois pas que le programme aurait tourné indéfiniment ; il montre seulement qu'il ne s'est pas arrêté pendant l'observation.

La décidabilité d'un problème porte sur l'existence d'un algorithme toujours correct et toujours terminant. Le comportement d'une seule exécution ne suffit pas à la trancher : un programme qui boucle fournit un cas d'arrêt négatif, pas à lui seul une preuve d'indécidabilité.

Le temps d'exécution mesure combien d'étapes demande un calcul qui termine. Le problème de l'arrêt pose d'abord une question binaire : le calcul finit-il ? Un programme peut terminer très lentement sans tourner indéfiniment.

Indécidable ne signifie pas insoluble dans chaque cas. Pour un programme qui s'arrête immédiatement, le verdict est direct. Le théorème exclut une méthode valable pour toutes les paires programme-entrée ; il n'interdit pas les preuves particulières.

Une longue attente n'est pas un verdict. Après n'importe quel temps fini, un programme encore actif peut soit s'arrêter plus tard, soit continuer indéfiniment. Il faut annoncer une limite d'observation, pas conclure automatiquement à une boucle infinie.

Restreindre le domaine change la question. Une méthode peut décider l'arrêt pour une classe limitée tout en échouant hors de cette classe. Il faut alors expliciter ses hypothèses au lieu de la présenter comme un règlement du problème général.

La machine universelle n'est pas le décideur impossible. Une machine de Turing universelle peut simuler d'autres machines. Le résultat de 1936 dit qu'aucun algorithme embarqué par elle ne peut toujours décider si chaque simulation finira.

La fiche machine de Turing présente le modèle de calcul dans lequel le problème est formulé.

La fiche décidabilité et indécidabilité replace ce théorème dans la classification des problèmes algorithmiques.

La fiche algorithme précise ce qu'est une procédure finie et pourquoi l'exigence de terminaison compte ici.