L'incomplétude mathématique/Le théorème fondamental de l’indécidabilité et le problème de Turing
Le théorème fondamental de l’indécidabilité établit l’existence d’au moins un ensemble indécidable.
À partir de l’existence d’un ensemble indécidable on ne peut pas conclure qu’il y a des problèmes mathématiques bien définis et néanmoins insolubles, mais seulement qu’il n’existe pas de méthode unique et bien définie pour répondre à toutes les questions, en nombre infini, qui portent sur certains ensembles bien définis.
Tous les théorèmes sur l’incomplétude de la prouvabilité axiomatique peuvent être considérés comme des corollaires des théorèmes d’existence d’ensembles indécidables. Le raisonnement est le suivant. Une théorie axiomatique T est toujours énumérable. Si elle est suffisamment riche, elle permet de définir un ensemble indécidable Indécid et son complémentaire C-Indécid. Si T était complète, elle contiendrait toutes les vérités sur C-Indécid. Comme T est énumérable, C-Indécid serait alors lui aussi énumérable. Mais C-Indécid n’est pas énumérable, parce qu'Indécid est indécidable. Il faut alors conclure que T est incomplète.
La présente section expose la preuve de Turing du théorème fondamental de l’indécidabilité. Cette preuve sera informelle. Pour une preuve complète, il faudrait préciser la notion de machine idéale de Turing, et prouver l’existence d’une machine de Turing universelle, ou ordinateur. Cette partie de la preuve n’est pas exposée ici parce que l’existence des ordinateurs est désormais couramment acceptée.
Il est possible de définir un ensemble énumérable Enum, et même décidable, de tous les noms des ensembles énumérables. On veut dire par là que l’on peut définir un formalisme dont le domaine d’objets est un ensemble EF d’expressions formelles, qu'Enum est une partie de EF, que toutes les parties énumérables de EF sont nommées par un élément de Enum, et qu'EF est suffisamment riche pour que tout ensemble énumérable concevable puisse être identifié à une partie énumérable de EF, par un processus simple de traduction. Il y a plusieurs façons de définir Enum. Nous présenterons celle de Turing.
Il est également possible de définir un ensemble VAEnum de toutes les vérités atomiques d’appartenance aux les ensembles énumérables. Le théorème fondamental de l’énumérabilité dit que VAEnum est énumérable. Autrement dit, l’ensemble de toutes les vérités atomiques d’appartenance aux ensembles énumérables est énumérable. Une vérité atomique d’appartenance sur les ensembles énumérables est une formule atomique vraie qui dit qu’une expression formelle appartient à l’ensemble énumérable nommé par une autre expression formelle. Nous montrerons plus loin que ce théorème est équivalent à celui de l’existence d’une machine de Turing universelle. Dans le chapitre suivant, nous donnerons une preuve de ce théorème à partir d’une autre définition de l’énumérabilité, équivalente à celle de Turing.
Le théorème fondamental de l’indécidabilité dit que VAEnum est indécidable. Autrement dit, l’ensemble de toutes les faussetés atomiques d’appartenance aux ensembles énumérables n’est pas énumérable. Appelons FAEnum cet ensemble. Une fausseté atomique d’appartenance est une formule atomique qui n’est pas vraie. À chaque fausseté atomique, on peut associer une formule vraie, qui dit qu’une expression formelle n’appartient pas à l’ensemble énumérable nommé par une autre expression formelle. Cette dernière formule n’est pas atomique mais presque parce qu’elle est la négation d’une formule atomique.
Nous allons d’abord présenter la méthode de Turing pour définir Enum. De cette méthode il résulte immédiatement que la vérité du théorème fondamental est équivalente à l’indécidabilité du problème de l’arrêt, ou problème de Turing. Il s’agit du problème de savoir par avance si oui ou non un ordinateur va s’arrêter et fournir un résultat. Turing a prouvé qu’on ne peut pas programmer un ordinateur pour savoir dans tous les cas si oui ou non un ordinateur va s’arrêter.
La méthode de Turing est facile à comprendre pour tous ceux qui savent programmer un ordinateur. Si on ignore les différences de capacité de mémoire et de temps de calcul, tous les ordinateurs sont équivalents, au sens où tout ce qui peut être fait par l’un peut aussi être fait par n’importe quel autre. En ce sens, les ordinateurs sont des calculateurs universels. On peut ignorer les différences de mémoire parce que celle-ci peut toujours être rallongée en connectant la machine à une banque de données. On peut ignorer les différences de temps de calcul dans la mesure où on s’intéresse seulement aux limites théoriques de la puissance des ordinateurs, comme si le fait d’attendre un résultat pendant des milliards d’années n’était pas un problème. Les ordinateurs sont équivalents parce qu’ils peuvent se représenter les uns les autres. On dit qu’une machine émule ou simule une autre machine. Turing a inventé la première technique de simulation d’une machine par une autre, avant même que les ordinateurs existent réellement.
Pour représenter une machine de Turing, il suffit de représenter son programme, c’est-à-dire la liste finie de toutes les règles qu’elle exécutera mécaniquement dès qu’elle aura été lancée.
Une machine de Turing peut être considéré comme une fonction qui à chaque état initial de la mémoire associe son état final, après que la machine se soit arrêtée. Le domaine de définition de cette fonction est l’ensemble de tous les états initiaux pour lesquels la machine s’arrête. Nous dirons que c’est aussi le domaine de définition de la machine. Un ensemble énumérable peut être représenté par une machine de Turing dont il est le domaine de définition. L’ensemble Enum est alors identifié à l’ensemble de tous les programmes, c’est-à-dire l’ensemble infini des listes finies d’instructions. Comme par définition de l’énumérabilité, un ensemble énumérable peut toujours être représenté par une machine de Turing, Enum ainsi défini est bien un ensemble de noms de tous les ensembles énumérables.
Dans une machine de Turing universelle U, la mémoire peut être divisée en deux parties, P et I . P sert à représenter le programme de la machine que l’on simule. Comme c’est une liste finie, P n’occupe qu’une partie finie de la mémoire totale. Le reste I sert à représenter l’état initial de la machine simulée. Après qu'U soit lancée, U s’arrête si et seulement si la machine représentée dans P s’arrête lorsque son état initial est celui représenté dans I. (Si U s’arrête le résultat qu'U fournit dans la partie I de sa mémoire représente le résultat fourni par la machine simulée par U .)
L’existence d’une machine universelle U montre que VAEnum est énumérable. Les énoncés atomiques sont représentés par les états initiaux de la mémoire de U. Un état initial représente l’énoncé que l’expression formelle représentée dans I appartient à l’ensemble énumérable représenté dans P. Les énoncés sont vrais lorsque U s’arrête, faux sinon.
Le théorème d’existence d’une machine universelle est donc équivalent au théorème fondamental de l’énumérabilité. Une machine universelle peut être conçue comme une sorte de diseur de vérités.
Par définition de la décidabilité, le problème de l’arrêt serait décidable si deux ensembles étaient énumérables, celui des couples (programme, état initial) pour lesquels une machine universelle s’arrête et celui des couples (programme, état initial) pour lesquels une machine universelle ne s’arrête pas. L’énumérabilité du premier est une conséquence directe de l’existence d’une machine universelle. Mais le théorème fondamental de l’indécidabilité affirme que le second ensemble n’est pas énumérable, qu’il ne peut pas exister de machine NegU qui représenterait FAEnum. Il est donc équivalent à l’indécidabilité du problème de l’arrêt.
Montrons que le paradoxe du menteur conduit à l’indécidabilité de VAEnum.
Si VAEnum était décidable, la machine NegU qui représente FAEnum existerait. On pourrait alors s’en servir pour construire une autre machine AT qui aurait la propriété suivante. AT s’arrête si et seulement si (l’ état initial de la mémoire de AT représente une machine M, par son programme, et M ne s’arrête pas lorsque son état initial représente la machine M elle-même). AT serait représentée par un programme PrAT. Turing a montré qu’il serait très facile d’écrire le programme PrAT si on avait le programme PrNegU de l’hypothétique NegU.
Supposons que l’état initial de la mémoire de AT soit chargée avec PrAT. Est-ce qu'AT va s’arrêter ? AT s’arrête si et seulement si (l’ état initial de la mémoire de AT représente une machine M, par son programme, et M ne s’arrête pas lorsque son état initial représente la machine M elle-même). Dans ce cas, la machine M est AT. On en conclut que, lorsque son état initial représente AT, AT s’arrête si et seulement si AT ne s’arrête pas. C’est une contradiction. L’hypothèse de l’existence de AT doit donc être rejetée, et par voie de conséquence l’existence de NegU aussi. Le problème de l’arrêt n’est donc pas décidable et FAEnum n’est pas énumérable. Autrement dit, VAEnum est indécidable.
En s’arrêtant après avoir été initialisé avec PrAT, la machine AT, conçue comme un diseur de vérités, dirait d’elle-même qu’elle ne s’arrête pas après avoir été initialisé avec PrAT. Il s’agit donc bien du paradoxe du menteur.
Le problème de l’arrêt est un problème concret, c’est un problème qui se pose quand on développe des programmes, ou logiciels. La preuve de son indécidabilité est donc une application concrète du paradoxe du menteur. Les paradoxes sont parfois considérés à tort comme des obstacles à l’avancement des sciences. C’est tout le contraire qui est vrai. Les paradoxes sont de très puissants moteurs pour la science.
