L'incomplétude mathématique/Les ensembles décidables et énumérables
On doit principalement à Turing l’approche de l’incomplétude que nous allons maintenant présenter. Elle permet de poser le problème de la prouvabilité dans toute sa généralité. Elle repose principalement sur la définition des ensembles énumérables.
Turing a conçu une machine idéale pour apporter une réponse précise et bien définie à la question, qu’est-ce qui est vraiment calculable ? Les ordinateurs ont été inventés ensuite. Ils sont une réalisation concrète de l’idée de Turing. La décidabilité et l’énumérabilité sont deux façons de préciser ce qu’on entend par la calculabilité.
Les ensembles décidables sont énumérables mais l’inverse n’est pas toujours vrai. Les différences entre ces ensembles viennent de la nature du critère d’après lequel on peut savoir quels éléments ils contiennent et ne contiennent pas. Si ce critère est efficace à la fois pour les affirmations et pour les négations, alors l’ensemble est décidable. Si ce critère est efficace seulement pour les affirmations alors l’ensemble est énumérable.
Il y a plusieurs façons équivalentes de donner une définition précise à cette notion d’efficacité des procédures de décision. Les découvertes de Herbrand, Gödel, Church, Post, Turing, et de beaucoup d’autres ont conduit à de telles définitions. La définition proposée par Turing sera présentée ici parce qu’elle est la plus facile à comprendre maintenant qu’aujourd’hui tout le monde ou presque connaît l’existence des ordinateurs. Dans le chapitre suivant, nous présenterons une autre définition, équivalente, inspirée des travaux de Post et de la thèse de doctorat de Smullyan, parce qu’elle est mieux adaptée à la méthode axiomatique.
Selon Turing, un ensemble E d’expressions formelles est décidable lorsqu’on peut programmer un ordinateur de telle façon que pour toute expression formelle x, la machine puisse répondre si oui ou non E contient x.
Si un ensemble est fini et si on connaît la liste de ses éléments alors il est décidable. Certains ensembles infinis sont également décidables, par exemple (l’ensemble de toutes les égalités x à la puissance y = z où x, y et z sont des entiers) est décidable. Il suffit de programmer un ordinateur pour qu’il calcule x à la puissance y et qu’il compare le résultat avec z.
On pense en général que les capacités de calcul d’un ordinateur sont limitées, à cause de la finitude de sa mémoire. Pour donner à sa définition toute la généralité de l’infini mathématique, Turing avait inventé le concept d’une machine dotée d’une mémoire infinie : un ruban de papier d’une longueur en principe illimitée. Le concept de Turing est à l’origine de l’invention des ordinateurs. On peut aussi considérer que leur mémoire est infinie, parce qu’on peut les connecter à des banques de données, dont la taille peut être augmentée indéfiniment. Avec une telle extension de mémoire, les ordinateurs peuvent faire tout ce que peuvent faire les machines idéales de Turing.
Un ensemble E est énumérable lorsqu’on peut programmer un ordinateur pour qu’il soit toujours capable de répondre oui si on lui présente le nom d’un élément de E et qu’il ne réponde jamais oui si on lui présente le nom d’un être qui n’est pas dans E. Mais dans ce dernier cas on n’exige pas que l’ordinateur réponde non. Il suffit qu’il ne réponde pas, il peut continuer à tourner indéfiniment sans jamais fournir de réponse.
On peut définir la décidabilité à partir de l’énumérabilité en disant qu’un ensemble est décidable si et seulement si lui-même et son complémentaire (dans l’ensemble de toutes les expressions formelles composées des mêmes symboles) sont énumérables.
Lorsqu’un ensemble est énumérable, on peut prouver pour tous ses éléments qu’il les contient. Les preuves consistent simplement à mettre en route la machine et à attendre qu’elle apporte les réponses souhaitées. Mais on ne sait pas a priori comment prouver qu’il ne contient pas certains éléments. Un simple mortel ne peut pas attendre une éternité. Si la machine continue à tourner, il ne sait pas a priori si elle va s’arrêter un jour et fournir un résultat ou si elle ne s’arrêtera jamais.
Une autre définition de l’énumérabilité consiste à dire qu’un ensemble est énumérable lorsqu’on peut programmer un ordinateur pour qu’il énumère, qu’il écrive par exemple, les noms de tous ses éléments. Si l’ensemble est infini, la machine ne s’arrête jamais, et consomme une quantité illimitée de papier.
Pour montrer que cette énumérabilité, appelons la liste-énumérabilité, est équivalente à la définition précédente, la oui-énumérabilité, il faut remarquer qu’on peut toujours programmer un ordinateur en mode multi-tâche. Plus précisément, on lui prescrit un temps de travail unitaire, disons 1 million d’opérations, et on lui prescrit d’examiner un ensemble infini de questions, en consacrant à chaque question un temps de travail unitaire. S’il ne trouve pas la réponse pendant ce temps limité, il conserve la question en mémoire et passe à la question suivante. On peut programmer un cheminement dans l’ensemble des questions tel que l’ordinateur revienne toujours aux questions auxquelles il n’a pas trouvé de réponses sans jamais cesser d’examiner de nouvelles questions et tel qu’il arrive ainsi à trouver les réponses à toutes les questions, en nombre infini, qui ont effectivement une réponse. Cela montre qu’un ensemble oui-énumérable est aussi liste-énumérable. La réciproque n’est pas difficile à prouver.
Une théorie axiomatique est toujours énumérable, pour les raisons suivantes. La liste, finie ou infinie, de ses axiomes, est toujours décidable, parce qu’on veut savoir précisément ce qui est et ce qui n’est pas un axiome. Les méthodes formelles imposent que les règles de déduction aient un caractère mécanique, qu’elles puissent être appliquées aveuglément par une machine. L’ensemble des preuves formelles est donc toujours décidable. Si on présente une preuve formalisée à un ordinateur convenablement programmé, il répond si oui ou non la preuve est correcte, si oui ou non elle commence par des axiomes et respecte les règles de déduction. La théorie, c’est-à-dire l’ensemble des théorèmes, ou formules prouvables à partir des axiomes, est énumérable, parce qu’on peut définir un ordre sur l’ensemble de toutes les listes finies de formules. Soit une formule F dont on veut savoir si elle est un théorème. L’ordinateur examine chaque liste finie de formules une par une et décide si oui ou non elle est une preuve formelle. Si oui, alors la dernière formule de la liste est un théorème. Si cette formule est F alors l’ordinateur s’arrête et répond que F est un théorème. Dans les autres cas, l’ordinateur examine la liste finie suivante. Si F est vraiment un théorème, un ordinateur ainsi programmé trouvera toujours la réponse, parce qu’il examine toutes les preuves formelles possibles. Mais il mettra beaucoup de temps, beaucoup trop pour que cette méthode soit réellement efficace pour nous simples mortels. Si F n’est pas un théorème, l’ordinateur ne s’arrête jamais, il examine sans arrêt de nouvelles listes, il trouve de nouvelles preuves, mais il ne trouvera jamais de preuve de F, puisque F n’est pas un théorème. Une théorie axiomatique est donc toujours énumérable mais il n’est pas sûr a priori qu’elle soit décidable.
Avant que la notion de décidabilité soit précisément définie, Hilbert avait espéré que l’on pourrait définir l’ensemble de toutes les vérités mathématiques comme un ensemble décidable. Gödel et ses successeurs ont montré qu’il existe des ensembles indécidables et que toutes les théories mathématiques suffisamment riches sont indécidables. Les ensembles décidables sont importants mais ils ne sont pas suffisants pour définir des théories suffisamment riches. Celles-ci sont des ensembles énumérables mais indécidables.
