Le problème de l’arrêt pose une question en apparence simple: peut-on construire un programme qui, en examinant n’importe quel autre programme accompagné de ses données de départ, déterminerait à coup sûr si celui-ci finira par s’arrêter ou bien continuera de tourner sans fin? Un programme peut en effet s’exécuter puis se terminer normalement, ou au contraire tomber dans une boucle infinie et ne jamais rendre la main. On aimerait donc un outil universel qui, sans lancer réellement l’exécution, prédirait dans tous les cas lequel de ces deux destins attend un programme donné. La réponse, démontrée mathématiquement, est qu’un tel outil ne peut pas exister: le problème de l’arrêt est indécidable.
Ce résultat a été établi par Alan Turing en 1936, dans le même article où il introduisait sa fameuse machine théorique. Son raisonnement repose sur un argument par l’absurde d’une grande élégance: en supposant qu’un programme détecteur d’arrêt existe, on peut s’en servir pour bâtir un programme paradoxal qui s’arrête exactement quand il ne devrait pas, et inversement, ce qui aboutit à une contradiction logique. Cette découverte s’inscrivait dans le prolongement des travaux de Kurt Gödel sur les limites des systèmes formels et fut l’une des premières démonstrations qu’il existe des tâches parfaitement bien posées qu’aucune machine ne pourra jamais accomplir dans leur généralité.
Loin d’être une curiosité abstraite, ce problème éclaire de nombreuses limites concrètes de l’informatique. Il explique pourquoi aucun logiciel ne peut garantir de repérer d’avance tous les programmes qui vont se figer, pourquoi les outils de vérification de code ne peuvent jamais prouver automatiquement l’absence de tout défaut, et pourquoi tant de questions générales sur le comportement des programmes se révèlent hors de portée d’une réponse automatique certaine. En pratique, les informaticiens contournent l’obstacle en se limitant à des cas particuliers, en imposant des délais maximaux d’exécution ou en acceptant des réponses qui ne sont sûres qu’une partie du temps.
Laisser un commentaire