Calculabilité et décidabilité : fiche de révision

1Un programme est une donnée

Un programme est un texte : on peut le stocker dans un fichier, le lire, le copier, le passer en argument à un autre programme. C'est ce que font un interpréteur (Python exécute le texte de votre script), un compilateur (il traduit un programme en un autre) ou un antivirus (il analyse des programmes). En Python, la fonction exec exécute une chaîne de caractères contenant du code.

Cette idée, formalisée par Turing dans les années 1930 (machine universelle capable de simuler n'importe quelle autre machine à partir de sa description), est le fondement de l'ordinateur : une même machine exécute tous les programmes au lieu d'être câblée pour une seule tâche.

Conséquence importante : on peut raisonner sur les programmes eux-mêmes (écrire un programme qui prend un programme en entrée et répond à une question sur lui). La suite du chapitre montre que certaines de ces questions n'ont aucune réponse algorithmique.

2Calculabilité et équivalence des langages

Une fonction est calculable s'il existe un algorithme (un programme) qui, pour toute entrée, termine et renvoie sa valeur. La thèse de Church-Turing affirme que tout ce qui est calculable « intuitivement » l'est par une machine de Turing, et donc par n'importe quel langage de programmation usuel.

Tous les langages de programmation généralistes (Python, C, Java, JavaScript…) sont équivalents en puissance de calcul : tout ce que l'un peut calculer, les autres le peuvent aussi. Ils diffèrent en lisibilité, performance, écosystème, mais pas en calculabilité. On dit qu'ils sont « Turing-complets » : il suffit pour cela de disposer des affectations, des tests, des boucles (ou de la récursivité) et d'une mémoire non bornée.

À l'inverse, un langage qui n'a que des boucles à nombre d'itérations fixé d'avance (sans while ni récursion) ne peut pas calculer toutes les fonctions calculables, mais garantit la terminaison de tous ses programmes. Il y a un compromis fondamental entre puissance d'expression et garantie de terminaison.

3Le problème de l'arrêt est indécidable

Un problème de décision est décidable s'il existe un programme qui répond oui ou non, correctement, pour toute entrée, en un temps fini. Le problème de l'arrêt demande : « étant donné un programme P et une entrée x, P s'arrête-t-il sur x ? » Turing a démontré en 1936 qu'aucun programme ne peut répondre à cette question dans tous les cas.

Démonstration par l'absurde. Supposons qu'il existe une fonction arret(P, x) qui renvoie True si P s'arrête sur x et False sinon. Construisons alors le programme D qui, recevant un programme P, boucle indéfiniment si arret(P, P) renvoie True, et s'arrête sinon. Que fait D appliqué à lui-même ? Si D(D) s'arrête, alors arret(D, D) est True, donc D boucle : contradiction. Si D(D) boucle, alors arret(D, D) est False, donc D s'arrête : contradiction. La fonction arret ne peut donc pas exister.

Il ne s'agit pas d'un manque de puissance des ordinateurs actuels : c'est une impossibilité mathématique, valable pour toute machine future. Elle explique pourquoi aucun outil ne peut détecter toutes les boucles infinies, tous les bugs ou tous les virus : ces problèmes se ramènent au problème de l'arrêt.

4Ce qu'il faut savoir répondre au bac

Les questions portent sur la compréhension des notions plutôt que sur des calculs : expliquer pourquoi un programme est une donnée avec un exemple (interpréteur, compilateur) ; définir calculable et décidable ; énoncer que le problème de l'arrêt est indécidable et en donner l'idée de la preuve ; expliquer pourquoi tous les langages sont équivalents ; distinguer « indécidable » (aucun algorithme ne peut répondre dans tous les cas) de « difficile » (un algorithme existe mais est lent).

Pièges : croire que l'indécidabilité vient de la lenteur des machines ; croire qu'on ne peut jamais savoir si un programme donné s'arrête (pour un programme particulier, on le sait souvent ; c'est le cas général qui est impossible) ; confondre calculabilité (existe-t-il un algorithme ?) et complexité (combien coûte-t-il ?) ; penser qu'un langage plus récent est « plus puissant » qu'un autre au sens de la calculabilité.