Peut-on décider de manière mécanique (à l’aide d’un programme) si un programme va s’arrêter un jour ? Peut-on décider si deux programmes font exactement la même chose ? Peut-on prouver que tel système d’exploitation ou tel logiciel de pilotage tournera toujours et ne plantera jamais ?
I. Preuves du théorème de l’arrêt
1) Preuve « moderne » par l’absurde
Supposons qu’il existe une fonction Python arret(prog, x) de code source qui termine toujours son exécution et retourne True si la fonction Python prog s’arrête lorsqu’on lui passe en argument x. Nous pouvons construire une nouvelle fonction diag(x) de la manière suivante :
Quel est le résultat de l’appel diag(diag) ?
Cet appel s’arrête si et seulement si arret(diag, diag) retourne False c’est-à-dire si et seulement si l’appel diag(diag) ne s’arrête pas. Nous sommes donc face à une contradiction !
Notre hypothèse qu’un tel programme existe est donc erronée : le problème de l’arrêt est indécidable !
2) Preuve de Turing
Turing a conçu une classe de machines de Turing particulières aux capacités surpuissantes : les machines de Turing universelles qui permettent de simuler le fonctionnement de toute autre machine de Turing sur une entrée au choix. Ces machines lui permettent de mettre en place un raisonnement similaire à celui que nous avons mené en Python pour aboutir à la même conclusion.
Parallèlement, Alonzo Church propose le modèle du λ-calcul dans lequel il mène un raisonnement le conduisant à une variante du même résultat (décider si deux programmes font exactement la même chose, quelles que soient leurs entrées). Les deux logiciens sont grandement influencés par le théorème d’incomplétude de Gödel établi quelques années auparavant.
II. Le théorème de Rice
Le théorème de Rice généralise l’indécidabilité du problème de l’arrêt. Il énonce que « toute propriété sémantique non triviale d’un programme est indécidable ».
Les propriétés sémantiques concernent le comportement d’un programme. Par exemple, il n’existe pas d’algorithme général répondant de manière systématique aux questions suivantes :
- « le programme ne renvoie jamais 42 » ;
- « le programme ne provoque jamais une erreur d’exécution » ;
- « le programme renvoie les mêmes résultats qu’un programme donné » ;
- « le programme contient un virus » ;
- « le programme accède à un site web ».
III. La thèse de Church-Turing
En langage simplifié d’aujourd’hui, la thèse de Church, rebaptisée ultérieurement thèse de Church-Turing, stipule que toutes les notions de procédures effectives, d’algorithmes que nous puissions imaginer sont calculables par des machines de Turing, ou des fonctions du λ-calcul, ou des programmes écrits en Python ou en Java ou dans n’importe quel autre langage de programmation.
Mot-clé
Une thèse consiste ici à affirmer, sans le démontrer, qu’une notion intuitive correspond exactement à une notion formelle. Toute démonstration est impossible, il est seulement possible de la falsifier ou d’apporter des arguments en faveur ou en défaveur.
Les fonctions calculées par tous les modèles de calcul envisageables coïncident, y compris les programmes que vous écrirez dans les futurs ordinateurs quantiques ! Les résultats décrits ci-dessus ont donc bien une portée universelle.
IV. Classes de complexité P et NP
Les machines de Turing constituent un outil important dans le domaine des classes de complexité algorithmique et en particulier dans la détermination des classes de problèmes que l’on peut résoudre dans un temps « raisonnable », c’est-à-dire qui augmente de façon polynômiale en fonction de la taille des entrées. On appelle cette classe P.
Une autre classe de problèmes est celle des problèmes difficiles dont le temps de calcul augmente exponentiellement en fonction de la taille des entrées, on appelle cette dernière classe de problèmes NP. Plus précisément, un problème de décision est NP s’il est décidé par une machine de Turing non déterministe en temps polynomial par rapport à la taille de l’entrée. On peut citer comme problèmes NP le problème du voyageur de commerce qui doit relier n villes ou le problème du sac à dos. Une des grandes questions ouvertes de l’informatique d’aujourd’hui est de savoir si P = NP.