Le paradoxe de Richard
Parmi les grands paradoxes qui ont ébranlé la logique et la théorie des ensembles au début du XXe siècle, le paradoxe proposé par Jules Richard en 1905 occupe une place centrale.
Considérons la structure de ce paradoxe. Soit l’ensemble des nombres réels; certains sont définissables en un nombre fini de mots. On peut, dans un premier temps, arithmétiser ces définitions en leur associant leur taille, à savoir le nombre de lettres qu’elles utilisent. Les définitions peuvent dès lors être ordonnées en fonction de leur taille. L’ensemble E qu’elles forment est dénombrable.
Il est alors possible, dans un deuxième temps, d’appliquer à E l’argument de la diagonale de Cantor, que l’on peut appeler C, et que Richard présente de la façon suivante :
Soit p, la n ième décimale du n ième nombre de l’ensemble E; formons un nombre ayant zéro pour partie entière, et pour n ième décimale p + 1, si p n’est égal ni à 8 ni à 9, et l’unité dans le cas contraire (Richard, Reference Poincaré and Heinzmann1992 [1905], p. 274).
On construit ainsi un nombre N qui n’appartient pas à cette liste ordonnée et donc n’appartient pas à E.
Dans un troisième et dernier temps, on remarque que la procédure de diagonalisation C, par laquelle nous avons pu construire N, vaut comme définition de N tout en étant de taille finie : C comporte un nombre fini de mots et donc de lettres. Par conséquent, N, qui a été construit en sorte de ne pas appartenir à E, appartient à E. On peut donc conclure sur une contradiction.
La solution de Poincaré
Richard réfute son propre paradoxe en expliquant que si N appartient à la liste, il occupe une certaine place G sur la liste. Mais à cette place, N est privé de sens puisqu’il suppose, pour être construit dans sa totalité, l’ensemble E achevé, or E n’est pas encore totalement achevé en G. Pour que N ait du sens, il faudrait pouvoir définir extensionnellement E, mais cela demanderait une infinité de mots et impliquerait donc la non-appartenance de N à la liste.
La solution donnée par Richard à son propre paradoxe est importante, car elle met Poincaré sur la voie d’une solution générale aux paradoxes logiques, solution qui va avoir une influence considérable sur les recherches qui seront entreprises pour surmonter ces paradoxes.
Cette solution est présentée dans son article «Les mathématiques et la logique» (Poincaré, Reference Poincaré and Heinzmann1986 [1906]). On peut décrire l’ensemble E comme l’ensemble de tous les nombres que l’on peut définir par un nombre de mots < n, n étant fini, mais à condition de ne pas introduire dans cette définition la notion de l’ensemble E lui-même; sinon, on a affaire à un cercle vicieux (ibid., p. 93). Or, un tel cercle vicieux apparaît dans la construction par diagonalisation du nombre N, qui suppose pour sa construction la liste totale des éléments de E à laquelle il se révèle finalement devoir appartenir. Il faut donc rejeter non seulement le paradoxe de Richard, mais aussi le processus de diagonalisation de Cantor et donc sa théorie des transfinis non dénombrables, à laquelle pourtant Poincaré avait été dans un premier temps favorableFootnote 1.
Or, cette solution de Poincaré peut être généralisée à l’ensemble des antinomies. Cela est évident dans le cas du paradoxe de Burali-Forti en 1897Footnote 2, puisque le paradoxe vient de ce que l’on systématise la démarche même de Cantor qui conduit aux cercles vicieux dénoncés par Poincaré. La même circularité peut être trouvée dans le paradoxe de Russell en 1902Footnote 3, puisqu’il suppose la possibilité de l’appartenance d’un ensemble à lui-même. Ainsi se trouve résolue la question des limites du lien entre définition et ensemble : toute définition ne peut produire un ensemble, seules les définitions prédicatives le peuvent. Or, une définition contenant un cercle vicieux n’est pas prédicative. Si un objet est défini par un ensemble auquel il appartient, sa définition modifie en retour l’ensemble sur lequel repose la définition et donc cette définition elle-même, etc., sans qu’il soit possible de stabiliser le processus sémantique.
Poincaré conclut son analyse en rejetant à la fois la logique formelle, qui reste stérile pour ne pas prendre en compte «l’intuition» — comprise dans un sens large, à la fois sensible et intellectuelFootnote 4 —, et le «Cantorisme», qui ne sauve la logique formelle de la stérilité que pour lui faire engendrer des antinomiesFootnote 5.
Si Russell ne suit pas Poincaré dans son mépris de la logique formelle et son rejet du cantorisme, il reprend toutefois son explication des paradoxes par la présence de cercles vicieux. Ainsi dans les Principia Mathematica (1910-1913), écrits avec Alfred North Whitehead, Russell affirme que le paradoxe a son origine dans la circularité et l’autoréférence, qui engagent un non-respect de la hiérarchie stricte des types construite par Russell :
Toutes ces contradictions (dont le nombre est tout à fait indéterminé) ont une caractéristique commune que nous pouvons appeler l’autoréférence, ou la réflexivité. [...] Ainsi toutes nos contradictions sont-elles des exemples de sophismes du cercle vicieux (Russell, Reference Russell and Whitehead1989 [1910], p. 303).
Influence du paradoxe de Richard sur le premier théorème d’incomplétude de Gödel
Loin toutefois de suivre cet interdit russellien, la démonstration du premier théorème d’incomplétude (syntaxique) de Gödel (1967 [1931]) repose précisément sur l’autoréférence et la circularité. Bien plus, elle se construit selon trois moments principaux (1. arithmétisation; 2. diagonalisation; 3. mise au jour de la contradiction) qui sont analogues structurellement aux trois moments constitutifs du paradoxe de Richard :
1.1. Gödel arithmétise, grâce à un codage numérique, la syntaxe du système formel des Principia Mathematica en y injectant l’ensemble des nombres naturels de l’arithmétique de Peano. Il attribue ainsi un nombre entier, dit nombre de Gödel, à tout signe du système, et donc à toute formule (en tant que suite finie de signes) et à toute démonstration (en tant que suite finie de formules). Cette attribution est bijective : à toute suite finie de signes correspond un nombre de Gödel et un seul, et à tout nombre de Gödel correspond une suite finie et une seule. On peut donc ordonner numériquement l’ensemble des suites finies de signes au sein du système.
1.2. Opérer toutefois ici la diagonalisation ne servirait à rien, car on dégagerait un nombre qui ne serait pas un nombre de Gödel, ce qui ne serait en rien contradictoire, puisque tout nombre n’est pas un nombre de Gödel. Pour pouvoir générer la contradiction, il faut étendre l’arithmétisation aux propriétés métamathématiques. De fait, si les objets sur lesquels portent les propriétés métamathématiques sont des nombres, les propriétés métamathématiques peuvent être interprétées comme des relations numériques et doncFootnote 6 être arithmétisées.
2. En recourant à un procédé circulaire analogue à la diagonalisationFootnote 7, Gödel construit une propriété métamathématique de non-démontrabilité à partir d’une liste de propriétés arithmétiques, et par arithmétisation, la réintroduit dans cette liste. Ce faisant, il la transforme en un énoncé arithmétique qui affirme qu’il n’existe pas de nombre codant sa propre démonstration. Ce qui revient à produire un énoncé autoréférentiel A qui affirme sa propre non-démontrabilité au sein du système, sur le modèle autoréférentiel négatif des ensembles qui ne se contiennent pas eux-mêmes dans le paradoxe de Russell ou de la proposition qui affirme sa propre fausseté dans le paradoxe du MenteurFootnote 8.
3. Comme dans les paradoxes de Russell et du Menteur, deux voies sont à considérer : l’énoncé A est ou bien démontrable, ou bien réfutable (sa négation est démontrable) au sein du système. S’il est démontrable au sein du système, A est vrai; or, il affirme sa non-démontrabilité, donc il est non démontrable au sein du système, ce qui correspond à une contradiction. Cette voie est à exclure, car nous avons supposé que notre système est cohérentFootnote 9. Reste la seconde voie : A est réfutable au sein du système. Mais cela implique de falsifier son contenu et d’affirmer qu’il est démontrable : on se retrouve à nouveau face à une contradiction, ce qui n’est pas davantage admissible, toujours en raison de notre hypothèse de cohérence. Par conséquent, on ne peut déduire des axiomes du système ni A, ni sa négation. En d’autres mots, A n’est ni démontrable, ni réfutable au sein du système.
Le raisonnement de Gödel, construit sur le modèle des paradoxes de Richard, de Russell et du Menteur, semble donc conduire à une aporie. Mais il n’en est rien, car le fait de n’être ni démontrable ni réfutable correspond à une propriété déterminée : l’indécidabilité Footnote 10. La véritable conclusion du raisonnement de Gödel est donc la découverte que A est indécidable au sein du systèmeFootnote 11. Or, reconnaître une telle indécidabilité de A, et donc notamment sa non-démontrabilité, c’est reconnaître la vérité de A, puisqu’il affirme précisément ne pas être démontrable. Le vrai doit alors être distingué du démontrable.
Le premier théorème d’incomplétude de Gödel affirme ainsi que tout système consistant (non contradictoire), formalisé et finitaire (donc susceptible d’un traitement machinique), et englobant l’arithmétique élémentaire (dans laquelle s’expriment les raisonnements finitaires) admet des propositions à la fois vraies et indécidables.
Insuffisance de la solution donnée par Richard à son paradoxe
Toute circularité n’est donc pas à interdire. Non seulement, ce serait un prix trop coûteux pour les mathématiques, mais il n’est en rien nécessaire pour obtenir le résultat souhaité : éliminer les paradoxes, puisque la forme paradoxale rencontrée par Gödel est surmontée par sa distinction entre démontrabilité et vérité.
Une telle interdiction de toute circularité ressemble ainsi à une thérapie trop forte et mal ciblée qui, par ses effets secondaires, présente plus d’inconvénients que d’avantages : on liquide la maladie, certes, mais on risque aussi de liquider le malade avec... Plutôt que de rêver à une hypothétique solution unique pour tous les paradoxes, il semble préférable de les prendre un par un, dans leur différence, et de leur appliquer une thérapie ciblée.
Revenons ainsi sur le paradoxe de Richard, dont la solution par Richard avait inspiré à Poincaré son rejet de toute circularité. Rappelons la solution de Richard. Le nombre N, construit par diagonalisation de l’ensemble E des réels définissables en un nombre fini de mots — et donc en dehors de E — doit cependant appartenir à E, puisque la procédure de diagonalisation s’énonce en un nombre fini de mots. Mais à la place G qu’il occupe, N est privé de sens puisqu’il suppose l’ensemble E achevé, et que E n’est pas encore totalement achevé en G. Pour que N ait du sens, il faudrait pouvoir définir extensionnellement E, mais cela demanderait une infinité de mots.
Cette solution est-elle valide? On peut en douter. En effet, elle revient à montrer que si l’on place le nombre N sur la liste, il est privé de sens. Mais cela, on le savait déjà, puisque le processus même qui préside à sa construction, et qui est identifié à sa «définition», interdit qu’il soit sur la liste. Le placer sur la liste est impossible. La solution de Richard ne fait que vérifier cette impossibilité. Elle résout donc moins la contradiction qu’elle ne la développe.
La solution de Peano
Il convient donc de trouver une autre solution, plus satisfaisante, au paradoxe de Richard. Poincaré revient en 1909 sur le paradoxe de Richard pour lui apporter une solution nouvelle, centrée non plus sur la circularité — sans doute en raison des objections de Peano et de Zermelo —, mais sur l’impossibilité d’une classification stable des définitions dans un ensemble infini, où l’ajout de nouveaux termes peut conduire à donner du sens à des phrases qui auparavant n’en avaient pas (Poincaré, Reference Poincaré and Heinzmann1986 [1909], p. 238). Poincaré redéfinit ainsi la prédicativité par la stabilité de l’opération de classification, tout en précisant à juste titre que cette stabilité n’est que relative et dépend du mode de définition.
Ces considérations sur la relativité de toute sémantique vont clairement dans le bon sens. Elles ont toutefois pour défaut de travailler, à la suite de Richard, sur une notion floue, celle de définition, en sorte que l’on peut rejeter le paradoxe en invoquant, à la suite de Peano, l’ambiguïté de la notion de «définition» utilisée par Richard, provenant du langage ordinaire et non d’un langage mathématique et formalisable. D’où la conclusion célèbre de Peano : «L’exemple de Richard ne concerne pas la mathématique mais la linguistique» (Peano, Reference Peano and Heinzmann1986 [1906], p. 120). Le paradoxe aurait donc sa racine dans le flou sémantique qui entoure ce terme de «définition», et les mathématiciens épris de rigueur devraient en tirer pour leçon la nécessité d’écarter, autant que possible, les termes du langage ordinaire en mathématique.
Cette solution de Peano est, somme toute, celle que reprend Zermelo dans son article «Nouvelle démonstration de la possibilité du bon ordre» (Zermelo, Reference Zermelo1992 [1908], p. 356). On peut la juger satisfaisante, mais elle reste imprécise et seulement négative, car elle ne nous permet pas de comprendre ce que l’on entend par «définir un objet». On peut se demander ce qui se passerait si l’on était en mesure de donner à cette expression une formulation conforme aux «lois fondamentales du domaine», comme le demande Zermelo.
Une solution «tarskienne»
Une autre solution fréquemment citée permet ici d’apporter une réponse. Elle remet en cause non pas le flou de la notion de définition, mais le fait que, dans ce paradoxe, la distinction hiérarchique mise en place par Tarski entre langage-objet et métalangage ne serait pas parfaitement respectée.
Ainsi, la diagonalisation porte sur l’ensemble E des réels définissables en un nombre fini de mots. N peut donc être défini comme «le réel que l’on peut construire par diagonalisation de la liste des éléments de l’ensemble des réels définissables en moins de n mots». Dès lors, lorsque, dans le troisième et dernier moment de son analyse, Richard remarque que N est définissable en moins de n mots, cela revient à dire que «le réel que l’on peut construire par diagonalisation de la liste des éléments de l’ensemble des réels définissables en moins de n mots» est définissable en moins de n mots.
Il apparaît alors que les deux occurrences de «définissable», à l’intérieur ou à l’extérieur des guillemets, ne sont pas de même niveau. La première relève du langage-objet et la seconde du métalangage. Il suffit donc de maintenir leur distinction, en refusant de considérer qu’un terme du métalangage puisse appartenir au langage-objet, pour lever le paradoxe. Le paradoxe de Richard trouve alors une solution analogue à la solution proposée par Tarski au paradoxe du MenteurFootnote 12.
Cette solution semble opératoire, mais elle a pour conditions une hiérarchie stricte entre les niveaux de langage et le rejet de toute circularité et de toute autoréférence, sur le modèle de la solution du paradoxe de Richard dans la théorie des types de Russell :
Quelle que soit la manière dont le type puisse être spécifié, «le plus petit ordinal qui n’est pas définissable au moyen de définitions de ce type» est une définition de type supérieur; et dans le paradoxe de Richard, quand nous nous limitons, ainsi qu’il le fait, aux nombres décimaux qui ont une définition d’un type donné, on s’aperçoit que le nombre N, qui est la source du paradoxe, reçoit une définition d’un type plus élevé, et donc ne tombe pas dans le domaine de nos définitions précédentes (Russell, Reference Russell and Whitehead1989 [1910], p. 306).
Une telle solution ne paraît pas toutefois évidente. Elle implique notamment de toujours pouvoir déterminer à quel niveau de langage un énoncé se situe, ce qui semble difficile. Quant à l’interdiction de toute circularité en sémantique entre langage et métalangage, on peut se demander s’il n’est pas possible de la contournerFootnote 13, tout comme l’interdiction analogue de circularité a été contournée en syntaxe par Gödel. D’autres voies paraissent possibles, qui peuvent peut-être se révéler plus fécondes.
Reformulation du paradoxe grâce à la théorie de la complexité de Kolmogorov
Si l’on choisit de ne pas suivre la voie tarskienne, il semble que l’on soit reconduit à la solution de Peano. Mais considérons plus attentivement cette notion de «définition» d’un nombre qui intervient dans le paradoxe de Richard.
On peut certes la rejeter en y voyant à la suite de Peano un concept linguistique flou. Le paradoxe est évité, mais l’intérêt de la solution est pauvre. La même approche — appliquée au dixième problème de Hilbert (1900), qui demande s’il existe «un procédé régulier» (Verfahren) permettant de distinguer par un nombre fini d’opérations si une équation diophantienne donnée est résoluble en nombres entiers — aurait conduit à rejeter ce problème en raison du caractère vague du terme «procédé régulier». Les logiciens ont préféré définir formellement ce termeFootnote 14, en comprenant le «procédé régulier» évoqué par Hilbert comme un algorithme, ce qui a permis à Youri Matiiassevitch d’apporter en 1970 une réponse négative, mais féconde, au problème de Hilbert.
Peut-on, de façon analogue, donner un sens plus rigoureux à la notion de «définition» d’un nombre, utilisée par Richard? On peut ici remarquer que le cœur de son analyse consiste à considérer que la procédure de diagonalisation de Cantor, par laquelle le nombre N est construit, correspond à une définition de N. Or, il est clair qu’une telle «définition» ne correspond pas à ce que l’on entend par «définition» en théorie du langage. Par «définition» d’un nombre, on peut ainsi légitimement supposer que Richard entend, sur un mode implicite et encore vague, la procédure algorithmique permettant de le construire. Telle est l’hypothèse que nous allons suivre afin de voir si elle nous permet d’apporter une solution plus féconde que celle de Peano au paradoxe de Richard.
Or, depuis la théorie de la complexité d’Andreï Kolmogorov (formulée en Reference Kolmogorov1965), il est possible d’arithmétiser une telle procédure algorithmique. Un nombre, retranscrit en base 2, est assimilable à une suite binaire finie. Or, cette dernière peut présenter ou non des régularités. Elle est plus ou moins ordonnée et plus elle est ordonnée, plus le programme permettant de la construire est court. La complexité d’une suite, au sens de Kolmogorov est la taille minimale du programme permettant de générer cette suite. Cette complexité est maximale lorsqu’on ne repère aucune régularité dans la suite et qu’il est impossible de la compresser (de réduire la taille du programme permettant de la construire). Le seul programme permettant d’écrire la suite S est alors le programme «imprimer S», dont la taille est aussi longue que la suite elle-même. Une telle suite est dite désordonnée ou aléatoire Footnote 15.
On peut alors reformuler le paradoxe de Richard de la façon suivante. Soit E l’ensemble des nombres que l’on peut construire par une procédure algorithmique finie, ou encore l’ensemble des nombres non aléatoires. On peut dans un premier temps construire la suite ordonnable et dénombrable de ses éléments en fonction de leur complexité croissante.
Notons ici que la notion de complexité permet de lever une ambiguïté majeure non envisagée par Richard, à savoir la possibilité pour un nombre d’avoir plusieurs «définitions» de taille variable. La complexité d’une suite numérique correspond en effet à la taille minimale du programme permettant de la construire, laquelle est unique même si un très grand nombre de programmes sont possibles.
Dans un second temps, on construit, par la procédure de diagonalisation, un réel qui n’appartient pas à cette suite. Cela nous conduit au troisième et dernier temps : comme l’énoncé du programme de la construction de N est finiFootnote 16, il semble que nous puissions en déduire l’appartenance de N à l’ensemble E, ce qui nous reconduit à la contradiction repérée par Richard.
Insuffisance d’une solution de type Richard
Toutefois, comme le soupçonne Richard dans sa propre résolution du paradoxe, ce n’est pas parce que l’énoncé linguistique du programme de la construction de N est fini que N est pour autant non aléatoire et donc appartient à E. Le soutenir serait confondre le point de vue linguistique et le point de vue algorithmiqueFootnote 17. Or, nous avons choisi de prendre la notion de «définition» au sens algorithmique. Suivant une telle approche algorithmique, le programme complet permettant de construire N fait intervenir la suite D qui s’écrit sur la diagonale.
Le paradoxe est-il résolu pour autant? Non, car ici, deux solutions se présentent : ou bien cette suite diagonale D est aléatoire, ou bien elle ne l’est pas. Lorsque Richard dit que la définition de N engagerait une définition infinie, il se place dans le premier cas, le plus favorable. La suite diagonale D étant aléatoire, le nombre N, correspondant à cette suite, est également un nombre aléatoire. Par conséquent, il n’appartient pas à E et le paradoxe est levé, sur le modèle de la solution initiale proposée par Richard en 1905.
En revanche, il est également possible que la suite diagonale D soit non aléatoire, et dans ce cas, le nombre N sera lui aussi non aléatoire. Dans ce cas de figure, N se trouve appartenir à E alors qu’il est construit en sorte de ne pas appartenir à E, et l’on retombe dans le paradoxe.
Une nouvelle solution
Du moins, il semble que l’on y retombe. Car nous pouvons imaginer ici une nouvelle solution à partir des résultats cruciaux de Gregory Chaitin (né en 1947) en théorie de la complexité algorithmique. Je vais présenter cette solution synthétiquement, sur un mode conceptuel.
Chaitin a montré — dans la continuité des travaux de Gödel et de Turing — qu’il n’est pas possible de dégager une méthode algorithmique générale permettant de mesurer la complexité de toute suite binaire finie. La détermination de la complexité de Kolmogorov en général est indécidable au sens algorithmique.
La notion de complexité de Kolmogorov ne peut donc avoir qu’un sens relatif et non absolu. Face à une suite qui nous semble incompressible et donc aléatoire, on ne peut jamais être absolument certain que l’on ne puisse découvrir un jour un algorithme permettant de la compresser.
Dès lors, l’ensemble E n’est pas récursivement énumérable Footnote 18. On ne peut donc dresser mécaniquement la liste de ses éléments, et a fortiori lui appliquer le processus de diagonalisation.
Le paradoxe de Richard se trouve ainsi levé — du moins dans la reformulation que nous en avons donnée — sans que l’on ait eu besoin de mettre en place à la suite de Tarski une hiérarchie stricte entre les niveaux de langage sur le modèle de la théorie des types, ou de renoncer à la circularité en mathématiques, circularité qui intervient déjà dans le théorème de Gödel, lequel utilise le processus de diagonalisation de Cantor.
Le paradoxe de Berry
Il convient ici de compléter notre étude en notant que la réflexion qui a conduit Chaitin à son résultat d’indécidabilité algorithmique est partie d’une réflexion menée au début des années 1970 non pas sur le paradoxe de Richard, mais sur celui de BerryFootnote 19. Ce paradoxe, suggéré par G. G. Berry, a été publié par Russell. En voici l’énoncé dans ses Principia Mathematica :
Le nombre de syllabes dans les noms anglais des entiers finis tend à augmenter avec les entiers, et doit augmenter graduellement de manière indéfinie, puisque seul un nombre fini de noms peut être atteint au moyen d’un nombre fini donné de syllabes. Aussi les noms de certains entiers doivent comprendre au moins dix-neuf syllabes, et parmi ceux-ci, il doit y en avoir un plus petit. Donc «le plus petit entier qui ne peut être nommé en moins de dix-neuf syllabes» doit dénoter un entier déterminé; en fait, il dénote 111 777. Mais «le plus petit entier qui ne peut être nommé en moins de dix-neuf syllabes» est lui-même un nom composé de dix-huit syllabesFootnote 20; aussi le plus petit entier qui ne peut être nommé en moins de dix-neuf syllabes peut l’être en dix-huit, ce qui est une contradiction (Russell, Reference Bennett1989 [1910], p. 302).
Il s’agit d’une version simplifiée du paradoxe de Richard qui ne fait plus appel à un ensemble infini. La question porte sur «le plus petit entier qui ne peut être nommé en moins de dix-neuf syllabes». Le paradoxe est que cette phrase définit cet entier en moins de dix-neuf syllabes. Ce qui est paradoxal.
La solution de Russell repose comme d’habitude sur le rejet de toute circularité, imposé par sa théorie des types :
Le paradoxe portant sur «le plus petit entier qui soit nommable en moins de dix-neuf syllabes» enveloppe, ainsi qu’on s’en aperçoit au premier coup d’œil, un cercle vicieux. Car le mot «nommable» se réfère à la totalité des noms, et cependant on lui permet de figurer dans ce qui prétend être l’un des noms. Aussi ne peut-il y avoir rien de tel que la totalité des noms, au sens où «noms» figure dans le paradoxe. Il est aisé de voir que, en vertu de la hiérarchie des fonctions, la théorie des types rend une totalité de «noms» impossible. [...] en aucun moment il n’est possible de donner un sens au mot «nommable» sans spécifier l’ordre des noms que l’on emploie; et n’importe quel nom dans lequel figure l’expression «nommable par des noms d’ordre n» est nécessairement d’un ordre plus élevé que n. Donc le paradoxe s’évanouit (Russell, Reference Russell and Whitehead1989 [1910], p. 305-306).
Là encore, on peut juger une telle solution, même si elle est efficace, trop brutale et trop coûteuse théoriquement.
La résolution par Chaitin du paradoxe de Berry
Pour traiter ce paradoxe, Chaitin suit une voie totalement différenteFootnote 21, inspirée par le premier théorème d’incomplétude de Gödel. Son premier souci est d’éviter la critique de Peano, et donc de quitter le plan linguistique pour un plan calculable. Plutôt que de considérer un locuteur du langage ordinaire, il considère donc un ordinateur, plus précisément une machine de Turing universelle standard.
Or, on peut déterminer rigoureusement ce que signifie définir (specifie) un nombre entier positif sur une telle machine. Un programme est dit définir un nombre entier positif si, lorsqu’on le fait tourner, il imprime au bout d’un temps fini ce nombre, qu’il écrit Stop et qu’il s’arrête. On n’a donc plus affaire à un texte du langage ordinaire dont on mesurerait le nombre de mots ou de syllabes, mais à un programme d’ordinateur que l’on mesure à partir de l’unité d’information, le bitFootnote 22.
La formulation du paradoxe peut donc être modifiée. La question porte désormais sur «le premier entier positif qui ne peut être défini sur une machine de Turing universelle par un programme en moins d’un million de bits». Par souci de simplicité, écrivons «définirMUT» pour «définir sur une machine de Turing universelle», et N bits pour «un million de bits». On s’interroge donc désormais sur : «le premier entier positif qui ne peut être définiMUT par un programme en moins de N bits».
Pour pouvoir échapper au paradoxe de Berry comme Gödel a échappé au paradoxe du Menteur, il convient d’opérer une nouvelle modification, analogue à celle opérée par Gödel dans son premier théorème d’incomplétude lorsqu’il substitue la non-démontrabilité à la fausseté. Soit le terme «démontrerSAF», qui signifie «démontrer dans un système axiomatique formalisé». La question à étudier porte désormais sur «le premier entier positif dont on peut démontrerSAF qu’il a la propriété de ne pouvoir être définiMTU par un programme en moins de N bits».
Or, pour calculer ce nombre, il faut élaborer un programme qui fait trois opérations successives :
1. passer en revue toutes les preuves possibles dans un système axiomatique formalisé, par ordre de taille;
2. appliquer un algorithme de test sur toutes ces preuves pour éliminer celles qui ne sont pas valides;
3. chercher la première preuve qu’un entier positif requiert au moins un programme de N bits.
La taille de ce programme ne dépend que de celle de ses deux composantes : un algorithme de test, qui est long de t SAF bits, et le nombre N qui est long de log2N bits. Le nombre total de bits du programme permettant de calculer le nombre que l’on recherche est donc : log2N + t SAF. Or, log2N + t SAF est beaucoup plus petit que N pour un N suffisamment grand (Chaitin, Reference Chaitin1995, p. 28). Cela est contradictoire, puisque ce nombre est défini comme ne pouvant être construit par un programme de moins de N bits. Qualifions un programme d’«élégant» s’il n’existe pas de programme plus court parvenant au même résultat. Le résultat de Chaitin revient à dire que l’on ne peut prouver qu’un programme est élégant.
Comme un nombre entier positif équivaut à une suite binaire finie, et comme, pour une telle suite, «pouvoir être définiMTU par un programme en moins de N bits» équivaut, en théorie de la complexité, à «avoir une complexité inférieure à N», on peut tirer du résultat de Chaitin qu’il n’existe pas de méthode algorithmique générale permettant de calculer la complexité d’une suite binaire finie.
Soyons attentifs au fait que le résultat obtenu par Chaitin n’est plus un paradoxe, tout comme le Menteur, une fois que Gödel a substitué la non-démontrabilité à la fausseté, n’est plus un paradoxe. Il correspond à la découverte positive d’une nouvelle forme d’indécidabilité mathématique, donc d’une nouvelle limite des systèmes axiomatiques formalisés.
La solution du paradoxe de Richard que nous avons proposée engage l’indécidabilité de la complexité algorithmique et repose donc en fin de compte sur la résolution par Chaitin du paradoxe de Berry. Son sens ne conduit pas à éliminer toute circularité en mathématique pour préserver l’intégrité de l’édifice mathématique contre les antinomies, mais au contraire à s’appuyer sur l’irréductibilité de la circularité pour découvrir — contre le modèle rationaliste et dans la continuité des travaux de Gödel — de nouveaux phénomènes positifs d’indécidabilité en mathématiques, lesquels n’ont fait que se multiplier durant la seconde moitié du XXe siècleFootnote 23. Une telle multiplication correspond non pas à un appauvrissement, mais à un enrichissement des mathématiques.
