(In)décidabilité

Les notions de décidabilité, de semi-décidabilité et d’indécidabilité concernent les problèmes de décision, c’est-à-dire les questions dont la réponse attendue est simplement oui ou non. Un problème est dit décidable lorsqu’il existe une procédure mécanique garantissant, pour n’importe quelle donnée qu’on lui soumet, de fournir la bonne réponse en un temps fini et de toujours s’arrêter. Vérifier si un nombre est pair, ou si un mot appartient à une liste donnée, sont des problèmes décidables. Un problème est semi-décidable, ou plus faible, lorsqu’on dispose d’une procédure qui répond correctement oui quand la réponse est oui, mais qui peut tourner indéfiniment sans jamais s’arrêter quand la réponse est non: on obtient la confirmation dans un sens seulement, l’absence de réponse ne permettant pas de conclure. Enfin, un problème est indécidable lorsqu’aucune procédure mécanique ne peut résoudre tous les cas, même en acceptant qu’elle prenne un temps très long.

Ces distinctions sont issues des recherches des années 1930 qui ont défini le calcul. En 1936, Alan Turing démontra que le problème de l’arrêt est indécidable: il n’existe aucun programme capable de déterminer, pour tout programme et toute donnée qu’on lui présenterait, si l’exécution finira par se terminer ou tournera sans fin. Ce résultat prolongeait les découvertes de Kurt Gödel sur les limites internes des systèmes logiques, et il établissait pour la première fois qu’il existe des questions parfaitement claires auxquelles aucune machine, si puissante soit-elle, ne pourra jamais répondre dans tous les cas. L’indécidabilité n’est donc pas une faiblesse temporaire de nos ordinateurs, mais une limite de principe.

Ces idées ont des conséquences très concrètes en informatique. Elles expliquent pourquoi aucun logiciel ne peut garantir de détecter à l’avance tous les programmes qui vont se bloquer, ni repérer avec certitude tous les virus possibles, ni prouver automatiquement l’absence de tout bug dans un code quelconque. Beaucoup de problèmes pratiques se révèlent indécidables dans leur forme générale, ce qui oblige à se contenter de solutions partielles: méthodes qui fonctionnent dans la plupart des cas, réponses approchées, ou restrictions du problème à des situations plus simples où une réponse sûre redevient possible.