Pour l a Science - n° 375 - Janvier 2009

LOGIQUE & CALCUL

Presque tout est indécidable !

Grâce aux notions probabilistes, les logiciens démontrent que l’incomplétude de Gödel est beaucoup plus grave et incontournable que tout ce que l’on pouvait craindre.

Jean-Paul DELAHAYE

 

L’incomplétude est l’incapacité, découverte et démontrée par Kurt Gödel, de concevoir un système mathématique qui capte toutes les vérités ma thématiques. Le hasard est l’incapacité, que chacun a expérimentée, de prévoir ce qui va arriver. Quels sont les liens entre ces deux concepts centraux de la philosophie et de la science moderne ?

À cette question, les logiciens proposent aujourd’hui trois faisceaux de réponses. Chacun d’eux suggère des idées en opposition avec la conception traditionnelle des mathématiques comme science dont les connaissances s’acquièrent par la démonstration.

Raisonnable, donc troué !

Découvert en 1930, le théorème d’incomplétude de Gödel affirme qu’en définissant de façon raisonnable ce que sont les preuves mathématiques, alors certaines vérités mathématiques échappent nécessairement à ces preuves.

Le mot « raisonnable » correspond à trois exigences. D’abord, on ne souhaite pas que les preuves conduisent à démontrer des affirmations contradictoires. Ensuite, on veut que les preuves permettent de démontrer les énoncés élémentaires vrais de l’arithmétique, par exemple que 25 est un carré, ou qu’il existe une infinité de nombres premiers. Enfin, si quelqu’un utilise cette définition des preuves pour démontrer un théorème, on exige que la preuve soit vérifiable sans risque d’erreur et d’une manière automatique. Ainsi, « raisonnable » pour un système de preuves signifie consistant, permettant de mener les raisonnements d’arithmétique élémentaire et mécanisable.

L’incomplétude démontrée par Gödel est avant tout une déception : elle affirme qu’avec une notion raisonnable de preuve mathématique, certaines vérités mathématiques ne pourront pas être prouvées : tout système raisonnable de preuves possède des trous. À y regarder de près, l’incomplétude de Gödel affirme un peu plus que la présence d’un trou dans tout système de preuves imaginables, elle affirme une « incomplétabilité ».

Le premier lien entre l’incomplétude et les probabilités que nous mentionnons précise justement cette « incomplétabilité ». Une conséquence directe du théorème de Gödel est qu’en ajoutant des vérités comme axiomes à l’aide d’un algorithme – qui éventuellement en ajoute progressivement une infinité – jamais on ne complète vraiment. Même après l’ajout, par un algorithme, d’une infinité d’axiomes à un système de preuves incomplet, le nouveau système de preuves obtenu, bien que plus complet, ne le sera pas totalement : il existera encore des énoncés mathématiques vrais qui ne seront pas démontrables avec la notion élargie de preuves.

Que se passe-t-il si l’on ajoute des axiomes au système que l’on veut compléter en utilisant le hasard ? Le hasard permettrait-il de compléter totalement ? Concrètement, l’idée est d’utiliser des algorithmes probabilistes, c’est-à-dire des procédés de calcul qui, de temps en temps, décident de l’opération à effectuer en tirant au hasard un bit 0 ou 1, en lançant une pièce de monnaie par exemple.

La réponse à cette question subtile a été brillamment élucidée par Leonid Levin (c’était le sujet de cette rubrique en mai 2007). L. Levin a montré que même en utilisant un algorithme probabiliste, on ne réussit jamais à compléter un système raisonnable de preuves. C’est notre première leçon sur les rapports du hasard et de l’incomplétude : le hasard ne permet pas de boucher le trou de l’incomplétude.

L’indécidabilité

Pour Leonid Levin, l’incapacité d’un système raisonnable de preuves à démontrer tout ce qui est vrai (théorème d’incomplétude de Gödel) ne peut être réparée ni par l’utilisation du hasard (méthode des algorithmes probabilistes) ni par l’utilisation d’un mécanisme physique et cela même si on le faisait fonctionner indéfiniment. Aucune machine, aussi étrange et complexe qu’elle soit, ne peut engendrer des formules qu’on ajouterait comme axiomes et qui à l’infini fournirait un système complet pour les mathématiques. L. Levin pense qu’à cause d’un principe de conservation de l’information, de telles machines ne peuvent pas exister, comme il ne peut pas exister de mouvement perpétuel à cause du principe de conservation de l’énergie.

Le hasard n’aidera pas à compléter

Dans l’esprit de L. Levin, ce résultat d’incomplétabilité possède une forme étendue. Pour lui, aucun système physique (même s’il fonctionne durant un temps infini) ne pourra compléter un système raisonnable de preuves : soit il donnera des contradictions, soit il laissera des trous. L.Levin conjecture un principe d’indépendance entre la physique et le monde mathématique s’appuyant sur une loi de conservation de l’information : aucun procédé physique ne crée de l’information avec suffisamment d’efficacité pour compléter un système incomplet. Pour lui, cette loi est aussi fondamentale que d’autres lois de conservation de la physique. Les arguments de L. Levin sont irréfutables dans le cas des algorithmes probabilistes, car ce sont des démonstrations mathématiques ; dans le cas plus général des procédés physiques quelconques, ces conjectures intéressantes n’ont sans doute pas été assez étudiées jusqu’à présent et aucun philosophe, à ma connaissance, ne les a analysées ou commentées. Ces arguments montrent que la limitation énoncée par le théorème de Gödel est plus grave qu’une simple limitation des systèmes de preuves : elle résulte d’un gouffre définitivement infranchissable entre le monde abstrait des mathématiques et celui de la physique.

La première réponse à notre interrogation est nette et négative : le hasard ne permet pas de combler le trou de l’incomplétude. La suite va confirmer la gravité, souvent insoupçonnée ou niée, de l’incomplétude logique découverte par Gödel.

LA PROBABILITÉ POUR QU’UNE FORMULE VRAIE de longueur n tirée au hasard soit indécidable tend vers 1 quand tend vers l’infini : à l’infini, toutes les formules sont indécidables.

La deuxième façon d’envisager la question des rapports entre incomplétude et probabilités est de se demander si l’incomplétude, finalement, ne serait pas un phénomène logique de peu d’importance du fait qu’elle ne concernerait que des énoncés « rares » ou qui surviennent avec une probabilité négligeable quand on les choisit « au hasard ».

Un système raisonnable de preuves étant fixé (par exemple l’arithmétique élémentaire de Peano ou la théorie des ensembles de Zermelo-Fraenkel), tombe-t-on fréquemment sur des indécidables ? Doit-on au contraire dire qu’ils sont rares ? Ces questions peuvent-elles recevoir une signification mathématique précise, par exemple à l’aide de formulations probabilistes ?

Cristian Calude, de l’Université d’Auckland en Nouvelle-Zélande, qui s’intéresse depuis longtemps à ce problème avec quelques collègues, a su y apporter plusieurs réponses. Celles-ci vont toutes dans le sens contraire de ce que nous désirions : un système S raisonnable de preuves étant fixé, alors une formule vraie y sera bien plus souvent indécidable que démontrable dans S. Il y a pire : l’indécidabilité, avec le système S, est quasi certaine dans l’ensemble infini des formules vraies !

La première série de résultats que C. Calude a obtenue avec Helmut Jürgensen, de l’Université d’Ontario au Canada, et M. Zimand, de l’Université de Townson aux États-Unis, a été mise au point et publiée en 1994. Elle signifie que pour tout système raisonnable de preuves et pour toute notion topologique « d’ensemble rare » adaptée aux considérations et aux objets de la logique, l’ensemble des formules vraies prouvables est un ensemble « rare » dans l’ensemble des formules vraies. L’indécidabilité est la règle majoritaire dans l’ensemble infini des formules vraies ; avec tout système raisonnable de preuves, les formules vraies démontrables sont une proportion négligeable des formules vraies. L’essentiel de ce qui est vrai est inaccessible. Non seulement tout système raisonnable de preuves est troué, mais typologiquement, un tel système n’est qu’un immense trou !

L’interprétation de cette découverte est incompatible avec l’idée que les mathématiciens se font de leur science. Le raisonnement mathématique permet certes de lier les vérités mathématiques – des axiomes (admis), on tire d’autres vérités (démontrées) grâce au travail de déduction –, mais les liens entre « peu d’hypothèses posées » et « beaucoup des vérités prouvées » sont ténus et partiels. Les mathématiciens sont fiers de leurs démonstrations, car ils croient qu’elles sont puissantes et générales et qu’elles constituent la méthode d’accès privilégiée aux vérités du monde abstrait. Le résultat sur la rareté des formules vraies démontrables indique que cette puissance est illusoire : à l’infini, les liens créés par le raisonnement mathématique sont d’une extrême inefficacité. Parmi les formules vraies qu’on aimerait capter dans un système de preuves, toutes, sauf une partie infinitésimale d’entre elles, sont indécidables. Le raisonnement mathématique n’établit pratiquement aucune déduction, sa puissance est une impression trompeuse résultant peut-être de ce que notre intérêt se limite au tout début de la liste infinie des formules vraies.

Le raisonnement n’est qu’une méthode limitée ne résolvant qu’une partie dérisoire du problème ! Les résultats de 1994 expriment une impuissance définitive du raisonnement mathématique. Notons que cette impuissance est démontrée par un raisonnement mathématique..., ce qui est un petit paradoxe !

Bien sûr, on peut répliquer que ce qui intéresse le mathématicien, ce ne sont pas tous les énoncés vrais, mais uniquement certains d’entre eux bien particuliers, et qu’en conséquence, la rareté topologique des énoncés démontrables n’est peut-être pas vraiment un handicap.

Une autre façon d’analyser le résultat sur la rareté des énoncés démontrables est de le voir comme la confirmation de la philosophie défendue par Gödel lui-même : faire des mathématiques, ce n’est pas seulement faire fonctionner le raisonnement à partir d’axiomes fixés une fois pour toutes, mais c’est aussi rechercher de nouveaux axiomes. Cette conception gödélienne des mathématiques comme quête de nouveaux énoncés à accepter sans preuve a été récemment illustrée par les travaux sur l’hypothèse du continu (voir cette rubrique en août 2008). À propos de ce problème, le travail du mathématicien aboutit à proposer l’adjonction de nouveaux axiomes à ceux traditionnellement considérés pour la théorie des ensembles. Le développement de la méthode expérimentale en mathématiques illustre aussi cette idée qu’il est utile d’envisager d’autres voies d’accès à la vérité que celle de la démonstration.

Une seconde série de résultats de C. Calude et H. Jürgensen (publiée en 2005) apporte un éclairage nouveau sur l’indécidabilité topologique de 1994 et vient la renforcer. Cette fois, la forte probabilité de l’incomplétude devient formulable en quelques mots simples, en même temps qu’une explication profonde du phénomène est proposée. C. Calude et H. Jürgensen ont donné un sens et une démonstration à l’idée avancée par Gregory Chaitin dès 1974 que l’incomplétude, dans certains cas, est la conséquence de la complexité.

La complexité, cause de l’indécidabilité

La longueur d’un énoncé mathématique E est le nombre de signes qu’il faut pour l’écrire : ainsi l’énoncé mathématique 1 + 6 = 7 est de longueur 5. La complexité de Kolmogorov K(E) d’un énoncé mathématique E est le nombre de signes du plus petit programme qui réalise l’impression de : ainsi la complexité de Kolmogorov de la suite 010101... 01 (01 répété 100 fois, donc de longueur 200) est le nombre de signes, dans le langage de programmation donné, de l’instruction « Imprimer 100 fois 01 ». C. Calude et H. Jürgensen mesurent la complexité d’un énoncé mathématique E par la différence d(E) = K(E) – longueur(E). Les énoncés dont la d-complexité est négative sont relativement simples, seuls ceux ayant une d-complexité positive sont complexes. Cette nouvelle mesure de complexité d’une formule ne remet pas en cause l’intérêt de K(E) qui, à bien des égards, reste plus naturelle, mais elle est la bonne façon de dire d’une formule qu’elle est vraiment complexe. Précisons que la complexité d(E) est souvent petite comparée à K(E), mais que cela n’empêche pas d(E) d’être parfois très grande et de dépasser n’importe quel nombre fixé à l’avance. Cette complexité conduit à la démonstration du remarquable résultat suivant : un système raisonnable de preuves ne peut démontrer que des énoncés E dont la complexité d(E) est inférieure à une constante k (dépendant du système en question).

Un concentré d’indécidabilité

L’incomplétude se manifeste parfois avec une force inouïe. C’est le cas avec le nombre Oméga (Ω) de Gregory Chaitin. Ce nombre est défini comme la probabilité qu’un programme tiré au hasard s’arrête. Pour tirer un programme au hasard, on procède de la manière suivante : on convient d’écrire les programmes en base 2 (par exemple en utilisant un codage binaire des caractères). Le tirage au hasard d’un programme consiste à choisir à pile ou face avec une pièce non truquée des « 0 » et des « 1 » jusqu’à avoir un programme complet, et ensuite à le faire fonctionner. Cela fixe une procédure précise permettant l’évaluation de Ω et cette procédure ne comporte aucune ambiguïté. Lorsque le langage de programmation et la convention de notation évoquée sont choisis, Ω est un être mathématique comme log(2) ou π. Puisque Ω est une probabilité, il est compris entre 0 et 1 et possède donc un développement binaire infini Ω = 0, a1  a2… an... La suite des chiffres de Ω est normale au sens de Borel : la fréquence avec laquelle on rencontre 0 ou 1 est 1/2, la fréquence avec laquelle on rencontre la séquence 00 (ou 01, ou 10 ou 11) est 1/4, et plus généralement la fréquence avec laquelle on rencontre une séquence déterminée de 0 et de 1 de longueur k est 1/2k. Le nombre Ω est transcendant (il n’est solution d’aucune équation polynomiale à coefficients entiers). Le nombre Ω est non calculable : aucun algorithme ne peut en égrainer les chiffres un à un. Le nombre Ω est aléatoire au sens de Per Martin-Löf (voir le texte). Le nombre Ω possède des chiffres qui, sauf pour un nombre fini d’entre eux, sont indécidables dans le sens suivant. Un système raisonnable de preuves peut déterminer certains chiffres de Ω, c’est-à-dire démontrer des énoncés du type « ai = 1» ou « ai = 0», mais un système raisonnable de preuves ne démontrera qu’un nombre fini d’énoncés de ce type. Pour presque tous les chiffres ai de Ω, l’énoncé vrai qui indique sa valeur (par exemple a1273 = 1) échappe à la théorie : elle ne le démontre pas, ni ne démontre sa négation ; pourtant Ω est défini de manière parfaitement précise et donc il est vrai que : soit ai = 0, soit ai = 1. Un système raisonnable de preuves ne peut quasiment rien savoir des chiffres de Ω, qui, de manière définitive, sont pour lui inconnaissables (sauf pour une quantité finie d’entre eux). Le nombre Ω de Chaitin est un cauchemar pour un esprit rationnel : il est « gravement indécidable », mais il existe des nombres Oméga qui sont pires. Associé à chaque système de preuves, le mathématicien Robert Solovay en a défini un qui est « le plus indécidable possible », on l’appelle le nombre Ω de Solovay. Son « inconnaissabilité » est absolue, car le système S auquel il est associé ne permet de connaître aucun chiffre de ce nombre. Dit autrement, tous les énoncés sans exception du type « ai = k » concernant les chiffres binaires de ce nombre sont des indécidables du système concerné. Pour les 60 ans de G. Chaitin, la médaille en haut à gauche a été gravée par ses amis. La première citation est Omne uno implicitur quod non attingitur ipsum, le « o » de « uno » est remplacé par « Ω » : « Tout est dans Ω, mais Ω n’est pas atteignable ». La seconde citation est Fortuita eveniunt vera mathematicae, soit « Les vérités mathématiques sont en réalité tortueuses ».

Dit autrement, toutes les formules trop complexes au sens de d sont indécidables. L’indécidabilité est donc conséquence de la complexité quand elle est mesurée par d. L’origine de l’indécidabilité, sa cause profonde, serait une trop grande complexité, affirmation qui n’est peut-être pas surprenante, mais qu’il est remarquable d’avoir formulé et démontré avec précision. Dès qu’un système raisonnable de preuves est fixé, la limite de son pouvoir de démonstration est aussitôt fixée par une constante k qui mesure le maximum de la complexité des formules que le système démontrera. Cela ne signifie pas que le système ne démontrera qu’un nombre fini de formules (c’est faux en général) ni d’ailleurs que toutes les formules vraies de complexité inférieure à k seront démontrables (certains indécidables sont assez simples), mais cela signifie que d(E) ne sera jamais grand si E est démontrable.

Il résulte alors assez simplement de ce résultat mentionnant d que si l’on note P(n) la proportion de formules de longueur n, vraies et démontrables dans un système raisonnable de preuves fixé S, alors P(n) tend vers 0 quand n tend vers l’infini. En d’autres termes : une formule vraie prise au hasard parmi les formules de longueur n a une probabilité P(n) d’être démontrable qui devient nulle quand n tend vers l’infini. À l’infini, toutes les formules vraies sont indécidables !

Cette seconde série de rapports entre probabilités et incomplétude aggrave ce que Gödel et L. Levin indiquaient sur la difficulté d’accès à la vérité mathématique. Les résultats et conceptions de L. Levin impliquent que le monde des vérités mathématiques est inaccessible depuis notre monde réel, soumis aux lois de la physique qui ne nous permettront jamais autre chose que l’utilisation de systèmes gravement incomplets et impossibles à compléter. Les résultats découverts par C. Calude et ses collègues signifient, de plus, que ces systèmes incomplets dont nous sommes obligés de nous satisfaire ne donnent accès, dans chaque cas particulier, qu’à une partie infinitésimale du monde mathématique !

Les suites tirées au hasard sont indécidables

Le troisième lien entre l’incomplétude et les probabilités est que tout ce qui est aléatoire est « essentiellement indécidable ».

Quelques précisions sont nécessaires pour donner un sens à cette affirmation. La notion de suite infinie aléatoire a été définie de manière précise grâce à la théorie de la calculabilité par Per Martin-Löf en 1966. Une suite binaire infinie (x0, x1,...,x ,...) est aléatoire si, à chaque fois que l’on considère la complexité de Kolmogorov des n premiers éléments de la suite, celle-ci vaut environ n, autrement dit si aucun début de la suite n’est compressible.

Voici maintenant le rapport entre ces suites aléatoires au sens de Martin-Löf et l’incomplétude. On suppose donné un système raisonnable de preuves S (par exemple celui de la théorie des ensembles ou celui de l’arithmétique élémentaire). Lorsqu’une suite (x) est aléatoire au sens de Martin-Löf, alors deux cas sont possibles :

– ou bien la suite (x) ne peut pas être définie dans S, et alors bien sûr on ne peut rien prouver dans S concernant (x) puisqu’on ne peut même pas en parler ! (ce cas n’est pas très intéressant, mais il ne faut pas l’oublier !).

– ou bien la suite (x) peut y être définie, ce qui est le cas par exemple des chiffres du nombre Oméga de G. Chaitin et alors, comme G. Chaitin l’a montré pour Oméga et C. Calude dans un cas plus général, le nombre de chiffres de la suite (x) que S permet de connaître est fini, autrement dit : (x) est essentiellement indécidable (voir l’encadré « Un concentré… »).

Si un procédé physique engendre une suite aléatoire (et en mécanique quantique on pense que de tels procédés existent) alors il engendre de l’indécidable. Par ailleurs, toutes les suites aléatoires qu’on peut définir en mathématiques avec précision (le nombre Oméga de G. Chaitin est une de ces suites) constituent des monstres d’indécidabilité.

Robert Solovay a d’ailleurs découvert une sorte de résultat ultime au sujet de l’indécidabilité des suites aléatoires. Son extraordinaire théorème indique qu’à tout système raisonnable de preuves S donné, est associé un nombre aléatoire Oméga(S), définissable dans S, mais tel que tous les énoncés de la forme « le n-ième chiffre de Oméga(S) est 0 » sont indécidables dans S. Ce nombre bien présent dans S et que S peut désigner est néanmoins totalement inaccessible dans le détail, par les moyens de preuves de S puisqu’aucun de ses chiffres n’est connu de S : dans ce nombre Oméga de Solovay, l’incomplétude et le hasard se rejoignent sous une forme extrême et absolue.

Le hasard et l’incomplétude sont deux formes différentes de l’ignorance forcée que la science moderne a dû admettre et qu’elle essaie de comprendre. Leurs liens sont puissants, nombreux et subtils. À chaque fois qu’on arrive à élucider un de ces liens – et les trois liens que nous avons mentionnés ne sont peut-être pas les seuls possibles –, on découvre des formes renforcées du résultat de Gödel de 1930.

Le vieux théorème d’incomplétude, loin de décrire un innocent phénomène ne concernant les mathématiques que de loin comme cela a parfois été dit, se révèle, année après année, plus profond, plus grave et plus fondamental, en même temps qu’il nous force à revoir nos idées sur la nature réelle des mathématiques et de leurs rapports avec la physique.

 

Jean-Paul DELAHAYE est professeur à l’Université de Lille et chercheur au Laboratoire d’informatique fondamentale de Lille (LIFL).

 

BIBLIOGRAPHIE

F. Dyson, What to Believe but Cannot Prove, J. Brockman,

Pocket Books, pp. 85-86, London, 2005, Voir http://www.edge.org/q 2005/q05_9.html#dysonf.

C. S. Calude, Incompleteness : A personal perspective, Centre for Discrete Mathematics and Theoretical Computer Science, Research Report Series CDMTCS 324, juin 2008.

J.-P. Delahaye, L’incomplétude, le hasard et la physique, Pour la Science, pp. 90-95, mai 2007.