Calculabilité et décidabilité

Un fichier source contient des caractères représentant des instructions. Pour un éditeur, ces caractères sont des données qu’il affiche ou modifie. Pour un interpréteur, ils décrivent les opérations à exécuter. Un compilateur transforme également la représentation d’un programme en une autre représentation. La distinction entre programme et donnée dépend donc de l’activité étudiée : le texte peut être traité par un autre programme avant ou pendant son exécution.

Télécharger un logiciel consiste à transmettre une représentation numérique. Le système peut la stocker, la copier ou l’examiner comme d’autres fichiers. Cela n’exige pas que le logiciel soit exécuté au moment du transfert. Cette possibilité permet aussi d’analyser des programmes : rechercher une instruction dans un texte, vérifier une syntaxe ou exécuter une simulation. Un programme recevant la description d’un autre programme n’est donc pas une idée contradictoire.

Nous notons P un programme et x une entrée. L’expression P(x) désigne l’exécution de P sur x. Lorsque l’entrée est une représentation de programme, il faut distinguer l’objet exécuté et la description fournie en donnée. Par commodité, on utilisera la même lettre pour le programme et sa description lorsque le contexte le précise. Ce choix de notation permet ensuite d’étudier l’exécution d’un programme sur sa propre description.

Un problème de décision attend une réponse oui ou non pour chaque entrée autorisée. Un décideur est un algorithme qui termine sur toute entrée du domaine et fournit toujours la bonne réponse. Ces deux exigences comptent : terminer en répondant au hasard n’est pas correct, et donner des réponses exactes seulement quand on arrive à terminer n’est pas une décision totale.

Un problème est décidable si un tel algorithme existe. Par exemple, déterminer si un entier naturel est pair est décidable : on calcule son reste dans la division par deux, puis on répond selon que ce reste vaut zéro ou un. Une fonction calculable est, dans le cadre étudié, une fonction dont les valeurs sont obtenues par un algorithme sur le domaine annoncé. Les domaines et le type de résultat doivent donc être spécifiés.

Pour prouver la terminaison d’un programme particulier, on peut souvent exhiber une quantité entière positive ou nulle qui diminue strictement à chaque étape tant que l’exécution continue. Si un compteur naturel n est diminué de un tant qu’il est strictement positif, il atteint zéro. Cet argument porte sur ce programme et ses entrées naturelles ; il ne résout pas le problème de terminaison pour tous les programmes possibles.

Exécuter un programme pendant une heure sans observer d’arrêt n’établit pas qu’il ne s’arrêtera jamais. Il peut avoir besoin d’une heure supplémentaire. Un délai maximal fournit une décision pratique d’abandon d’un essai, pas un décideur mathématique du problème général de l’arrêt. Inversement, observer un arrêt fini prouve la terminaison de cette exécution particulière, sans prouver celle de toutes les entrées.

Le problème général de l’arrêt demande, à partir d’un programme P et d’une donnée x, si l’exécution P(x) termine. On suppose pour raisonner par contradiction qu’un programme H répond correctement et termine pour chaque couple (P, x). Il renvoie oui si P(x) s’arrête et non sinon. H doit lui-même toujours terminer : sans cette exigence, on ne disposerait pas du décideur annoncé.

Grâce à la possibilité de traiter un programme comme une donnée, on construit alors un programme D recevant la description d’un programme Q. D demande à H si Q(Q) s’arrête. Si H répond oui, D se met à boucler sans fin. Si H répond non, D termine immédiatement. La construction est décrite à partir des opérations supposées disponibles : appeler H, tester sa réponse, terminer ou effectuer une boucle infinie.

La question décisive concerne D exécuté sur sa propre description. On demande donc à H ce qu’il prédit pour le couple (D, D). Il ne s’agit pas d’attendre que la machine réalise une infinité d’étapes. On examine séparément les deux réponses possibles d’un outil que l’on a supposé correct et toujours terminant.

L’indécidabilité du problème général n’interdit pas de prouver la terminaison de nombreux programmes particuliers. Le compteur décroissant en fournit un exemple. Elle n’interdit pas non plus les outils utiles d’analyse ou de vérification. Un outil peut être exact sur une famille de programmes limitée, refuser certains cas ou renvoyer une réponse inconnue. Ce qu’il ne peut pas promettre dans le modèle est une réponse exacte et toujours obtenue pour toutes les entrées du problème général.

Changer un langage de programmation général pour un autre ne supprime pas cette limite lorsqu’ils possèdent les mêmes possibilités algorithmiques dans le modèle idéal. Une notation plus courte, un langage plus rapide ou un processeur plus puissant peuvent changer la facilité de programmation et le temps de calcul. Ils ne transforment pas la contradiction logique précédente en un algorithme correct. Les ressources physiques finies d’un ordinateur réel et les modèles théoriques doivent cependant rester distingués.

Il faut aussi distinguer indécidable et coûteux. Un problème peut posséder un algorithme qui termine toujours, tout en nécessitant un temps considérable. La question existe-t-il un algorithme total correct précède alors la question combien de ressources utilise-t-il. Confondre ces niveaux conduit à conclure trop vite qu’un calcul impossible à finir sur son ordinateur n’est pas calculable.

S’entraîner : utilise la rubrique Exercices du site. La prochaine leçon revient à la construction de programmes récursifs dont on peut analyser les appels et la terminaison.