Le hasard en arithmétique & le déclin et la chute du réductionnisme en mathématiques pures [1]


Gregory J. Chaitin, chaitin@watson.ibm.com

Bulletin of the European Association for Theoretical Computer Science (EATCS), No. 50 (June 1993), pp. 314-328

Lecture donnée le jeudi 22 octobre 1992 à l'occasion d'un colloque sur les Mathématiques et l'Informatique tenu à l'Université de New Mexico. La lecture a été enregistrée sur vidéo et le texte suivant est une transcription de l'enregistrement.

1. Hilbert et la méthode axiomatique

J'ai donné le mois dernier une conférence au cours d'un symposium sur le réductionnisme à Cambridge, là où Turing a effectué son travail. J'aimerais reprendre les propos que j'ai tenu là-bas et expliquer en quoi mon travail poursuit et prolonge celui de Turing. Deux conférenciers précédents avaient dit du mal de David Hilbert. Aussi commençai-je par dire qu'en dépit de ce que les auditeurs pouvaient avoir entendu lors de certaines des lectures précédentes, Hilbert n'était pas un idiot !

L'idée de Hilbert constitue le point culminant de deux mille ans d'une tradition mathématique qui remonte au traitement axiomatique de la géométrie par Euclide, ainsi qu'au rêve leibnizien d'une logique symbolique et au monumental Principia Mathematica de Russell et Whitehead. Le rêve de Hilbert était d'éclaircir une fois pour toutes les méthodes du raisonnement mathématique. Il souhaitait rendre explicite un système axiomatique formel qui aurait contenu toutes les mathématiques.

Un système axiomatique formel
-->
-->
-->

Hilbert mettait l'accent sur un certain nombre de propriétés essentielles qu'un tel système axiomatique formel devait posséder. Leur description ressemble à un langage de programmation. Il s'agit d'un énoncé précis des méthodes de raisonnement, des postulats et des méthodes d'inférence que les mathématiciens acceptent. Hilbert spécifiait en outre que le système axiomatique formel qu'il souhaitait construire afin de contenir toutes les mathématiques devait être "consistant" et "complet".

Un système axiomatique formel
--> consistant
--> complet
-->

"Consistant" signifie que vous ne pouvez pas prouver une assertion et son contraire.

Un système axiomatique formel
--> consistant A ¬A
--> complet
-->

Vous ne devez pas pouvoir prouver A et non A. Ce pourrait être très embarrassant.

"Complet" signifie que si vous effectuez une assertion sensée, vous devez pouvoir en décider d'une manière ou d'une autre. Cela signifie que soit A soit non A doit être un théorème, doit être démontrable à partir des axiomes en utilisant les règles d'inférence du système axiomatique formel.

Un système axiomatique formel
--> consistant A ¬A
--> complet A ¬A
-->

Considérez une assertion sensée A et son contraire non A. L'une des deux exactement doit être démontrable si le système axiomatique est consistant et complet.

Un système axiomatique formel est comme un langage de programmation. Il comporte un alphabet et des règles de grammaire, ou en d'autres termes, une syntaxe formelle. C'est le genre de choses avec lesquelles nous sommes maintenant familiers. Jetez un oeil aux trois énormes volumes rédigés par Russell et Whitehead  ; ils sont remplis de symboles, et l'on a l'impression de contempler un vaste programme d'ordinateur écrit dans une sorte de langage de programmation incompréhensible.

Un fait très surprenant apparaît alors. La consistance et la complétude se rapportent à la vérité, à toute la vérité, et semblent constituer des exigences raisonnables. Il existe cependant une conséquence amusante ayant trait au "problème de la décision" que l'on l'appelle en allemand l'Entscheidungsproblem.

Un système axiomatique formel
--> consistant A ¬A
--> complet A ¬A
--> le problème de la décision

Hilbert attribuait une très grande importance au problème de la décision.

HILBERT
Un système axiomatique formel
--> consistant A ¬A
--> complet A ¬A
--> le problème de la décision

Résoudre le problème de la décision pour un système axiomatique formel, c'est donner un algorithme qui permette de décider si une quelconque assertion sensée est un théorème ou non. Une solution au problème de la décision est appelée une procédure décisionnelle.

HILBERT
Un système axiomatique formel
--> consistant A ¬A
--> complet A ¬A
--> une procédure décisionnelle

Cela semble tout de même curieux. Le système axiomatique formel que voulait construire Hilbert aurait inclus toutes les mathématiques : l'arithmétique élémentaire, le calcul, l'algèbre, absolument tout. Si une procédure décisionnelle avait existé, les mathématiciens auraient alors été réduits au chômage. Cet algorithme, cette procédure mécanique aurait permis de vérifier qu'une expression quelconque est ou non un théorème, de décider si elle est vraie ou non. Réclamer ainsi une procédure décisionnelle pour un tel système axiomatique formel paraît être un réquisit démesuré.

Il est cependant très facile de voir que si un système axiomatique formel est consistant et complet, cela implique qu'il doive exister une procédure décisionnelle. Voici comment procéder. Prenons un langage formel possédant un alphabet fini et une grammaire. Hilbert insistait sur le fait que l'intérêt essentiel d'un système axiomatique formel est qu'il doive exister une procédure mécanique pour vérifier si une preuve supposée est correcte ou non, si elle obéit aux règles ou non. Il s'agit là de la notion selon laquelle la vérité mathématique doit être objective de telle manière que n'importe qui puisse être d'accord sur le fait qu'une preuve suive (ou non) les règles instituées.

Si tel est le cas, vous parcourez toutes les preuves possibles en ordre croissant de taille et vous examinez toutes les séquences de symboles de l'alphabet de longueur un, deux, trois, quatre, mille, mille un, ..., cent mille caractères. Vous appliquez la procédure mécanique, qui est l'essence même du système axiomatique formel, afin de vérifier si chacune de ces preuves est valide. La plupart du temps, bien sûr, il s'agit d'un pur non-sens et l'expression considérée n'est même pas grammaticalement correcte. Mais vous trouverez incidemment toutes les preuves possibles. Cela ressemble à un million de singes qui tapent à la machine. Vous découvrirez ainsi toutes les démonstrations possibles, tout au moins en principe. Car le nombre croît de façon exponentielle et c'est donc une tâche que l'on ne pourrait pas réaliser en pratique ; on ne peut pas obtenir de cette manière une preuve qui soit longue d'une page, par exemple.

En principe donc, vous pourriez explorer toutes les preuves possibles, vérifier celles qui sont valides et examiner ce qu'elles démontrent ; de cette manière, vous pourriez découvrir systématiquement tous les théorèmes. En d'autres termes, il existe un algorithme, une procédure mécanique qui permette de générer un par un chaque théorème démontrable dans un système axiomatique formel. Si, pour toute assertion sensée du système, soit cette assertion soit son contraire est un théorème - et une et une seule l'est -, vous possédez une procédure décisionnelle. Pour déterminer si une assertion est un théorème ou non, vous déroulez toutes les preuves possibles jusqu'à ce que vous constatiez que l'assertion se révèle être un théorème ou que vous démontriez le contraire de l'assertion en question.

Hilbert semble bien avoir estimé effectivement qu'il était sur le point de résoudre tous les problèmes mathématiques une fois pour toutes. Cela paraît ahurissant, mais il semble bien qu'il l'ait cru. Il pensait qu'il serait capable de produire un système axiomatique formel consistant et complet pour toutes les mathématiques et qu'il pourrait obtenir à partir de celui-ci une procédure décisionnelle pour toutes les mathématiques. Cette ambition procède tout simplement de la tradition axiomatique formelle en mathématiques.

Je suis cependant certain qu'il ne pensait pas que la procédure décisionnelle en question puisse être une procédure pratique. Ce que je viens d'esquisser marcherait seulement en principe. Car c'est exponentiellement long, terriblement long ! C'est absolument impraticable. Mais l'idée sous-jacente était que si tous les mathématiciens pouvaient se mettre d'accord sur ce qu'est une preuve correcte ainsi que sur la consistance et la complétude, cela fournirait en principe une procédure décisionnelle pour résoudre automatiquement n'importe quel problème mathématique. C'était le rêve magnifique de Hilbert qui constitue le point culminant de la tradition qui mène d'Euclide à Russell et Whitehead en passant par Leibniz, Boole et Peano.

Le seul problème bien sûr avec ce projet qui stimule l'imagination, c'est qu'il s'est révélé être impossible !

2. Gödel, Turing et l'argument de la diagonale de Cantor

Hilbert est véritablement une source d'inspiration. Sa fameuse lecture donnée en 1900 constitue pour les mathématiciens un appel aux armes afin de résoudre une liste de vingt-trois problèmes difficiles. Lorsque vous lisez cette liste de vingt-trois problèmes quand vous êtes jeune débutant, Hilbert vous assure qu'il n'existe aucune limite à ce que peuvent faire les mathématiciens. Nous sommes en mesure de résoudre un problème si nous sommes assez intelligent et si nous y travaillons suffisamment longtemps. Il ne croyait pas qu'il existât en principe une limite à ce que les mathématiques pourraient réaliser.

J'estime que ce projet est vraiment une grande source d'inspiration. Ainsi pensait John von Neumann qui a tenté dans sa jeunesse de réaliser l'ambitieux programme de Hilbert. Et parce que celui-ci ne pouvait pas tout mener à bien, il s'attaqua à la théorie élémentaire des nombres, 1, 2, 3, 4, 5, ..., plutôt qu'aux nombre réels.

En 1931, à la surprise de tous - y compris de John von Neumann -, Gödel a montré comme chacun sait que c'est impossible, que cela ne peut être réalisé [2] .

Gödel 1931

Tout le monde attendait le contraire, et Von Neumann a dit par exemple qu'il ne lui était jamais venu à l'esprit que le programme de Hilbert ne puisse être mené à bien. Von Neumann admirait énormément Gödel et l'aidât à obtenir un poste permanent à l'Institute for Advanced Study de Princeton.

Gödel a démontré le résultat suivant. Supposons que vous ayez un système axiomatique formel capable d'exprimer la théorie élémentaire des nombres - c'est-à-dire 1, 2, 3, 4, 5, ..., muni de l'addition et de la multiplication. Admettons également que ce système soit consistant ; c'est une exigence minimale, car si vous pouviez démontrer des résultats faux ce serait assez fâcheux. Gödel a montré que si vous supposez ce système consistant, alors vous pouvez démontrer qu'il est incomplet. C'est là le résultat de Gödel et la preuve en est très astucieuse et fait appel à l'autoréférence. Gödel a été capable de construire une assertion à propos des nombres entiers qui exprime par elle-même qu'elle n'est pas démontrable. Ce fût un choc énorme. On a admiré Gödel pour son imagination intellectuelle car tout le monde en dehors de lui pensait que Hilbert avait raison.

Je pense cependant que l'approche effectuée par Turing en 1936 est meilleure.

Gödel 1931
Turing 1936

La preuve donnée par Gödel en 1931 est très ingénieuse ; c'est un véritable tour de force [3] . Lorsque, jeune garçon, j'essayais de comprendre cette démonstration, je dois avouer que je pouvais lire celle-ci et la suivre pas à pas, mais d'une manière ou d'une autre, je n'ai jamais réellement éprouvé que je la saisissais véritablement. Turing avait une approche complètement différente.

Je pense qu'il est juste de reconnaître que l'approche de Turing est à certains égards plus fondamentale. Turing en réalité a fait plus que Gödel. Il n'a pas seulement obtenu un corollaire du résultat de Gödel, mais il a également montré qu'il ne peut exister de procédure décisionnelle.

Supposez en effet que vous ayez un système axiomatique formel capable d'exprimer l'arithmétique et qui soit consistant ; vous savez d'après le théorème de Gödel qu'il ne peut pas être complet, mais il pourrait encore exister une procédure décisionnelle. Il pourrait encore y avoir une procédure mécanique qui permettrait de décider si une assertion est vraie ou non. Gödel avait laissé ouverte cette possibilité, mais Turing l'a résolu. Le fait qu'il ne puisse exister une procédure décisionnelle est plus fondamental que l'incomplétude et vous pouvez en déduire ce dernier résultat comme un corollaire.

Comment Turing a-t-il fait ? Je souhaite décrire de quelle façon il a procédé car il s'agit d'un tremplin pour mon propre travail. Je suis sûr que tout le monde a entendu parler de sa démarche qui a trait à ce que l'on appelle désormais le "problème de l'arrêt" (halting problem [4] ). En réalité, si vous relisez l'article de Turing publié en 1936, vous ne trouverez pas les mots halting problem. Mais l'idée s'y trouve manifestement.

On oublie également que Turing parlait de "nombres calculables". Le titre de son article est d'ailleurs On computable numbers, with an application to the Entscheidungsproblem (Théorie des nombres calculables, suivie d'une application au problème de la décision [5] ). Tout le monde se souvient que le halting problem est indécidable et que ce résultat provient du papier en question, mais peu de gens se rappellent que Turing traitait des nombres réels calculables. Mon propre travail a trait aux nombres réels calculables et aux nombres réels qui sont non calculables de manière spectaculaire. Je souhaite donc rappeler maintenant la démonstration de Turing.

Le raisonnement de Turing a véritablement détruit le rêve de Hilbert ; et c'est un raisonnement simple. Il s'agit uniquement de la méthode de la diagonale de Cantor - pour ceux qui savent ce que c'est - appliquée aux nombres réels calculables. Voilà en bref toute l'idée, et cela est suffisant pour montrer que le rêve de Hilbert, le point culminant de deux mille ans de pensée mathématique est faux. Le travail de Turing est donc extrêmement profond.

Quel est ce raisonnement ? Un nombre réel, par exemple 3,1415926..., est une longueur mesurée avec une précision arbitraire, c'est-à-dire avec un nombre infini de chiffres. Et, nous dit Turing, un nombre réel calculable est un nombre réel pour lequel il existe un programme d'ordinateur ou un algorithme qui permette d'en calculer les chiffres un par un. Il existe par exemple des programmes d'ordinateurs pour calculer le nombre pi, et il existe également des algorithmes pour déterminer les solutions d'équations algébriques ayant des coefficients entiers. À vrai dire, la plupart des nombres que l'on rencontre effectivement en Analyse sont calculables. Il existe cependant des exceptions, car si vous connaissez la théorie des ensembles, les nombres réels calculables sont dénombrables tandis que les réels ne le sont pas (il n'est pas nécessaire de savoir ce que cela signifie). Voici donc quel est l'essentiel de l'idée de Turing.

Plus précisément, l'idée est la suivante. On dresse la liste de tous les programmes possibles. Il n'existait pas de programmes d'ordinateurs à l'époque et Turing a dû inventer la "machine de Turing" qui a constitué un formidable bond en avant. Mais actuellement vous pouvez imaginer que l'on écrive la liste de tous les programmes possibles :

p1
p2
p3
p4
p5
p6
...
Gödel 1931
Turing 1936

Si l'on considère qu'un programme d'ordinateur est écrit en binaire, il est alors naturel de penser à un programme comme à un nombre. Et devant chacun de ces programmes, le premier, le second, le troisième, etc., on écrit le nombre réel qu'il calcule si tant est qu'il en calcule un (il peut ne pas le faire). S'il imprime un nombre infini de chiffres, on écrit ces chiffres. Il s'agit peut-être de 3,1415926..., puis un autre chiffre, et un autre, et encore un autre...

p1 3,1415926...
p2 ...
p3 ...
p4 ...
p5 ...
p6 ...
...
Gödel 1931
Turing 1936

Notre liste est maintenant écrite. Certains de ces programmes n'impriment peut-être pas un nombre infini de chiffres car il y a des programmes qui se terminent ou qui sont erronés et "se plantent". Ils constitueront alors des lignes blanches dans la liste.

p1 3,1415926...
p2 ...
p3 ...
p4 ...
p5
p6 ...
...
Gödel 1931
Turing 1936

Ce n'est pas vraiment important ; on peut oublier cette possibilité.

En suivant Cantor, Turing considère la diagonale en envisageant le premier chiffre du premier nombre, le second chiffre du second, le troisième chiffre du troisième, etc.

p1 -, d 11 d12 d13 d14 d15 d16 ...
p2 -, d21 d 22 d23 d24 d25 d26 ...
p3 -, d31 d32 d 33 d34 d35 d36 ...
p4 -, d41 d42 d43 d 44 d45 d46 ...
p5
p6 -, d61 d62 d63 d64 d65 d 66 ...
...
Gödel 1931
Turing 1936

Il s'agit effectivement des chiffres qui se trouvent après la virgule décimale. On considère donc le premier chiffre après la virgule du premier nombre, le second chiffre après la virgule du second nombre, le troisième chiffre du troisième nombre, le quatrième chiffre du quatrième, le cinquième du cinquième. Il n'est pas important que le cinquième programme ne produise pas de cinquième chiffre ; cela n'a véritablement aucune importance.

Modifiez maintenant ces chiffres. Choisissez-les différents et changez chaque chiffre de la diagonale. Assemblez ensuite ces chiffres modifiés pour former un nouveau nombre avec une virgule décimale au début, c'est-à-dire un nouveau nombre réel. Tel est l'argument de la diagonale de Cantor. Vous avez donc choisi un chiffre différent du premier chiffre du premier nombre, un second chiffre différent du second chiffre du second nombre, etc., et vous avez regroupé ces chiffres afin de constituer un autre nombre.

p1 -, d 11 d12 d13 d14 d15 d16 ...
p2 -, d21 d 22 d23 d24 d25 d26 ...
p3 -, d31 d32 d 33 d34 d35 d36 ...
p4 -, d41 d42 d43 d 44 d45 d46 ...
p5
p6 -, d61 d62 d63 d64 d65 d 66 ...
...
, ¬=d11 ¬=d22 ¬=d33 ¬=d44 ¬=d55 ¬=d66 ...
Gödel 1931
Turing 1936

Par la manière dont il a été construit, ce nouveau nombre ne peut pas figurer dans la liste précédente. C'est, pour cette raison, un nombre réel non calculable. Mais comment Turing est-il passé de cette constatation au halting problem ? En fait, demandons-nous pourquoi ne peut-on pas calculer ce nombre ? J'ai indiqué comment l'obtenir et il semblerait que l'on puisse presque le calculer. Pour évaluer le nième chiffre de ce nombre, on prend le nième programme - on peut certainement faire cela - et on commence à l'exécuter jusqu'à ce qu'il produise un nième chiffre ; à ce stade enfin, on modifie le chiffre. Où est donc le problème ? Cela semble facile.

Le problème est celui-ci : que se passe-t-il si le nième programme ne produit jamais un nième chiffre et que vous restiez assis ici à l'attendre ? C'est là qu'intervient le halting problem ; on ne peut pas déterminer si le nième programme produira jamais un nième chiffre ! Turing a montré ainsi que le halting problem ne peut pas être résolu. Parce que si vous pouviez résoudre le halting problem, vous pourriez décider si le nième programme produit un nième chiffre. Et si vous pouviez faire cela, vous pourriez effectivement mener à bien la procédure de la diagonale de Cantor et calculer un nombre réel qui diffère de tous les nombres réels calculables. Voilà quel est le raisonnement original de Turing.

En quoi cela fait-il voler en éclat le rêve de Hilbert ? Qu'a donc prouvé Turing ? Qu'il n'existe pas d'algorithme, de procédure mécanique qui permettrait de décider que le nième programme puisse produire un nième chiffre. Ainsi donc, il n'existe pas d'algorithme qui permettrait de décider qu'un programme quelconque s'arrête (le fait pour le nième programme d'exhiber le nième chiffre est un cas particulier). Or Hilbert appelait de ses voeux un système axiomatique formel dont toute vérité mathématique découlerait (uniquement la vérité mathématique, mais toute la vérité mathématique). Si Hilbert avait pu réaliser cela, nous aurions obtenu une procédure mécanique pour décider si un programme s'arrête. Et pourquoi donc ?

On parcoure donc toutes les démonstrations possibles jusqu'à ce que l'on trouve une preuve que le programme se termine ou une preuve qu'il ne s'arrête jamais. Ainsi donc, si le rêve hilbertien d'un ensemble fini d'axiomes dont on pourrait dériver toutes les vérités mathématiques est possible, alors, en explorant toutes les démonstrations possibles et en vérifiant toutes celles qui sont correctes, on serait capable de déterminer si un programme s'arrête. En principe, on pourrait réaliser cela. Mais on ne le peut pas en vertu du raisonnement très simple de Turing qui n'est rien que l'argument de la diagonale de Cantor appliqué aux nombres réels calculables. C'est aussi simple que cela !

La démonstration de Gödel est ingénieuse et difficile. La preuve que l'on doit à Turing est par contre si fondamentale et si profonde que tout y semble naturel et inévitable. Son travail repose cependant sans conteste sur celui de Gödel.

3. La probabilité d'arrêt et le hasard algorithmique

J'ai évoqué Turing et les nombres réels calculables parce que j'utilise une méthode différente pour fabriquer un réel non calculable, un réel beaucoup plus "incalculable" que ceux de Turing.

p1 -, d 11 d12 d13 d14 d15 d16 ...
p2 -, d21 d 22 d23 d24 d25 d26 ...
p3 -, d31 d32 d 33 d34 d35 d36 ...
p4 -, d41 d42 d43 d 44 d45 d46 ...
p5
p6 -, d61 d62 d63 d64 d65 d 66 ...
...
, ¬=d11 ¬=d22 ¬=d33 ¬=d44 ¬=d55 ¬=d66 ...
Gödel 1931
Turing 1936
Les nombres réels non calculables

Voici donc comment nous allons nous attirer des ennuis encore pires.

Comment puis-je obtenir un réel beaucoup plus "incalculable" ? (et je devrais encore expliquer jusqu'à quel point il n'est pas calculable). En dehors de l'argument de la diagonale de Cantor, considérons le nombre suivant que j'aime appeler Oméga :

Oméga = Somme p s'arrête 2 - |p|

Il s'agit uniquement de la probabilité d'arrêt, et cette notion constitue une espèce de calembour mathématique. Le résultat fondamental de Turing est que le halting problem ne peut pas être résolu ; il n'existe aucun algorithme qui déciderait du halting problem. Mon résultat essentiel est que la probabilité d'arrêt est algorithmiquement irréductible ou algorithmiquement aléatoire.

Qu'est-ce donc exactement que cette probabilité d'arrêt ? Je viens d'écrire son expression :

Oméga = Somme p s'arrête 2 - |p|

Au lieu d'examiner les programmes individuellement et de se demander s'ils se terminent, vous mettez tous ces programmes ensemble dans un sac. Si l'on génère alors un programme au hasard en lançant en l'air une pièce de monnaie pour déterminer chacun de ses bits, quelle est la probabilité pour que le programme en question s'arrête ? Pensez à un programme comme à une chaîne de bits ; on génère chacun des bits grâce au jet d'une pièce, de telle manière que si le programme a une longueur de N bits, la probabilité pour que l'on engendre ce programme soit 2-N. Tout programme p qui s'achève contribue pour 2-|p| (deux élevé à la puissance de sa taille en bits, c'est-à-dire le nombre de bits qu'il possède) à cette probabilité d'arrêt.

En procédant ainsi, il apparaît un détail technique très important qui ne marchait pas dans la première version de la théorie algorithmique de l'information. On ne pouvait pas écrire dans cette version l'expression suivante :

Oméga = Somme p s'arrête 2 - |p|

Cette somme aurait engendré une valeur infinie. Le détail technique en question est le suivant : aucune extension d'un programme valide n'est un programme valide. Dans ces conditions, la somme

Somme p s'arrête 2 - |p|

est comprise entre 0 et 1. Dans le cas contraire, elle diverge vers l'infini. Dix années seulement se sont écoulées avant que je n'obtienne la formulation correcte. La version originale de la théorie algorithmique de l'information, qui date des années soixante, est fausse. Et l'une des raisons en est que l'on ne pouvait même pas définir le nombre :

Oméga = Somme p s'arrête 2 - |p|

J'ai remanié la théorie algorithmique de l'information en 1974 à l'aide de la notion de self-delimiting program et j'ai alors découvert la probabilité d'arrêt Oméga.

Il s'agit donc bien d'une probabilité comprise entre 0 et 1 :

0 < Oméga = Somme p s'arrête 2 - |p| < 1 (comme pour toute probabilité)

L'idée consiste à générer chacun des bit d'un programme par le jet d'une pièce de monnaie et de se demander quelle est la probabilité pour que cela se termine. Ce nombre Oméga, cette probabilité d'arrêt n'est pas seulement un nombre réel non calculable ; Turing savait déjà comment obtenir de tels nombres. Il est incalculable de la pire des manières qui soit et je vais maintenant donner quelques indices afin de comprendre à quel point il n'est pas calculable.

Le première chose à remarquer est que ce nombre est algorithmiquement incompressible. Si vous cherchez à produire les N premiers bits de Oméga à l'aide d'un ordinateur, si vous désirez concevoir un programme qui imprime les N premiers bits de Oméga et ensuite s'arrête, ce programme devra avoir une longueur de N bits. Fondamentalement, vous pouvez juste imprimer les constantes qui sont incluses dans le programme. Vous ne pouvez pas compresser les N premiers bits de Oméga. Ce nombre

0 < Oméga = Somme p s'arrête 2 - |p| < 1

est un nombre réel que l'on peut écrire en binaire. Et si l'on souhaite produire ses N premiers bits à l'aide d'un programme, on doit les y incorporer au départ. Le programme doit avoir une longueur de N bits. C'est une information algorithmique irréductible. Il n'en existe aucune description concise.

Mais tout ceci est une manière abstraite de parler de ces choses. Voici maintenant un exemple plus concret du caractère aléatoire de Oméga. Émile Borel fut au début du siècle l'un des fondateurs de la théorie des probabilités.

0 < Oméga = Somme p s'arrête 2 - |p| < 1
Émile Borel

Question : Puis-je poser une question très simple avant que vous ne poursuiviez ?

Réponse : Bien sûr.

Question : Je ne vois pas pourquoi Oméga devrait être une probabilité. Qu'en est-il si les deux programmes ayant un bit de longueur s'arrêtent tous les deux ? Je veux dire : que se passe-t-il si les deux programmes de longueur un bit s'arrêtent et qu'un autre programme s'arrête également ? Oméga est alors plus grand que un et n'est donc pas une probabilité.

Réponse : Je vous ai dit qu'aucune extension d'un programme valide n'est un programme valide.

Question : Ah oui, c'est vrai, aucun autre programme ne peut alors s'arrêter.

Réponse : Les deux programmes de longueur un bit seraient dans ce cas les seuls programmes à envisager. C'est pourquoi le nombre

0 < Oméga = Somme p s'arrête 2 - |p| < 1

ne peut pas être défini si vous considérez les programmes de façon correcte...

Ainsi donc, Émile Borel avait étudié ce qu'il appelait les nombres normaux.

0 < Oméga = Somme p s'arrête 2 - |p| < 1
Émile Borel --- les nombres réels normaux

Qu'est-ce qu'un nombre réel normal ? On a calculé pi au-delà du milliard de décimales, peut-être jusqu'à deux milliards. En dehors du fait que cela ressemble à grimper sur une montagne et à détenir ainsi un record du monde, l'une des raisons de ce genre d'exploit consiste à se demander si chacun des chiffres apparaît avec la même occurrence dans la suite des décimales. Il semble bien que chacun des chiffres de 0 à 9 intervient avec une fréquence de 10 % dans le développement décimal du nombre pi. "Il semble", dis-je, car personne n'a pu le prouver. Je pense que la même chose est vraie pour le nombre 2½ bien qu'il ne s'agisse pas d'un nombre aussi populaire que pi pour se poser ce genre de question.

Je vais maintenant décrire un travail réalisé par Borel au début du siècle alors qu'il était le précurseur de la théorie moderne des probabilités. Tirez au hasard un nombre réel à l'intérieur de l'intervalle unité, c'est-à-dire un nombre réel possédant une partie décimale mais pas de partie entière. Si donc on choisit un nombre réel dans cet intervalle unité, Borel a montré qu'il est "normal" avec une probabilité égale à un. "Normal" signifie que lorsque l'on écrit ce nombre en base 10, chaque chiffre apparaît avec la fréquence limite de 10 % exactement. Ceci est également vrai dans toutes les autres bases ; par exemple en binaire, 0 et 1 se présenteront avec une fréquence limite de 50 % chacun. Et il en est de même avec les blocs de chiffres. Borel appelait "réel absolument normal" ce genre de nombre et il a montré que la probabilité d'en tirer un au sort entre 0 et 1 est égale à un. Mais il y a un problème. Il ne savait pas si pi est normal ou si 2½ est normal. En fait, il ne pouvait pas exhiber un seul exemple de nombre réel normal.

Le premier exemple de nombre réel normal a été découvert par David Champernowne, un ami d'Alan Turing à Cambridge. Champernowne est d'ailleurs toujours vivant ; c'est un économiste bien connu. Turing était impressionné par celui-ci (je crois bien qu'il l'appelait "Champ") parce qu'il avait publié sa découverte alors qu'il était encore étudiant. Ce nombre est appelé nombre de Champernowne ; le voici :

0 < Oméga = Somme p s'arrête 2 - |p| < 1
Émile Borel --- les nombres réels normaux
Champernowne
0,01234567891011121314...99100101...

Il est formé de la façon suivante : après la virgule décimale, vous écrivez 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, puis 10, 11, 12, 13, 14, ..., jusqu'à 99, ensuite 100, 101, etc. Et vous continuez de cette manière amusante. C'est ainsi qu'est composé le nombre de Champernowne et celui-ci a montré qu'il est normal en base dix, et uniquement en base dix. Personne ne sait s'il est normal dans d'autres bases. Je crois qu'il s'agit là d'un problème encore ouvert. En base dix, pourtant, non seulement les chiffres 0 à 9 apparaîtront avec une fréquence de 10 % exactement, mais chacun des blocs possibles de deux chiffres apparaîtra avec une fréquence de 1 %, chacun des blocs possibles de trois chiffres apparaîtra avec une fréquence de 0,1 %, etc. C'est ce que l'on appelle "être normal" en base 10. Mais personne ne sait ce qu'il en est dans d'autres bases.

J'ai exposé tout ceci pour la raison suivante : le fait que la probabilité Oméga soit une information algorithmiquement irréductible entraîne que ce nombre

0 < Oméga = Somme p s'arrête 2 - |p| < 1

est normal dans chacune des bases. Ceci est facile à montrer en utilisant des idées sur le codage et la compression de l'information qui remontent à Shannon. Nous avons donc finalement obtenu un exemple de nombre absolument normal. Je ne sais pas à quel point vous le trouvez naturel, mais ce nombre réel spécifique s'est avéré normal au sens le plus fort imaginé par Borel. Il se pourrait qu'il n'en soit pas tout à fait de même pour le nombre de Champernowne.

Ce nombre Oméga est en fait aléatoire selon plusieurs autres acceptions de ce terme et je souhaite maintenant dire un mot en ce sens. Oméga ne peut pas être distingué du résultat d'une série de jets indépendants d'une pièce de monnaie parfaitement équilibrée. Ce nombre

0 < Oméga = Somme p s'arrête 2 - |p| < 1

montre en réalité qu'il existe un hasard absolu, un certain chaos, une totale imprévisibilité et un manque de structure au sein même des mathématiques pures ! De la même manière que le seul argument de la diagonale a suffit à Turing pour détruire le rêve de Hilbert, il suffit d'écrire l'expression

0 < Oméga = Somme p s'arrête 2 - |p| < 1

pour montrer qu'il existe des régions des mathématiques pures où le raisonnement est totalement inutilisable, où vous vous heurtez à un mur impénétrable. Voilà tout ce qu'il en est de la probabilité d'arrêt.

Pourquoi ai-je affirmé cela ? Supposons que vous souhaitiez utiliser des axiomes pour démontrer ce que sont les bits du nombre Oméga. J'ai déjà dit que ce nombre, comme celui que Turing a construit en utilisant l'argument de la diagonale de Cantor, n'est pas calculable. Nous savons donc qu'il n'existe pas d'algorithme qui permettrait de le calculer chiffre après chiffre ou bit après bit. Essayons maintenant de déterminer ce que sont ces bits en utilisant un système axiomatique formel. Que se passe-t-il ?

La situation est alors extrêmement mauvaise. Supposons en effet que l'on dispose d'un système axiomatique formel qui constitue les N bits d'un autre système axiomatique formel (j'expliquerai plus loin ce que cela signifie plus précisément). Il en découle alors qu'avec un système axiomatique formel de complexité N, c'est-à-dire un système axiomatique formel de longueur N bits, on peut établir les positions et les valeurs de N + c bits au plus de Oméga.

Qu'entend-on par "système axiomatique formel de longueur N bits" ? Souvenons-nous qu'un système axiomatique formel concrétise une procédure mécanique permettant de vérifier si une preuve formelle suit ou non certaines règles. C'est un programme d'ordinateur. Il n'existait pas bien sûr de programmes du temps de Hilbert, mais après que Turing eût inventé les machines qui portent son nom, on pouvait finalement détailler très précisément la notion de programme - et bien entendu nous sommes maintenant tout à fait familiers avec ce concept.

Ainsi donc, l'algorithme de vérification d'une preuve - qui est l'essence même de tout système axiomatique formel au sens de Hilbert - est un programme. Examinons maintenant quelle est la longueur en bits de ce programme [6] . Ce problème est foncièrement identique à la question de savoir combien de bits sont nécessaires pour spécifier les règles du jeu, c'est-à-dire les axiomes, les postulats et les règles d'inférences. Si ce programme a une longueur de N bits, alors on est capable de montrer par exemple que le premier bit de Oméga est un 0 binaire, que son second bit est 1, que le troisième est 0, (là je dois laisser un vide...), et l'on pourra être à même de prouver que le millième bit est 1. Mais on ne sera capable d'établir que N cas si le système axiomatique formel est un système de N bits.

Je vais essayer d'expliquer un peu mieux ce dernier point. Cela signifie que vous ne pouvez pas obtenir en sortie plus que ce que vous mettez en entrée. Si vous voulez montrer qu'un bit particulier d'une position spécifique du développement binaire du nombre réel Oméga est 0 ou 1, la seule manière de le démontrer est de le considérer comme une hypothèse, un axiome, un postulat. Il s'agit d'une information mathématique irréductible ; c'est la phrase-clé qui résume toute cette idée.

Information mathématique irréductible
0 < Oméga = Somme p s'arrête 2 - |p| < 1
Émile Borel --- les nombres réels normaux
Champernowne
0,01234567891011121314...99100101...

Qu'avons-nous donc obtenu ? Nous possédons un objet mathématique assez simple qui nous échappe complètement. Les bits du nombre Oméga ne possèdent aucune structure. Il n'existe aucun modèle, aucune organisation que nous autres mathématiciens pourrions comprendre. Si nous voulons montrer ce que sont les bits de ce nombre à telle ou telle place, s'ils sont égaux à 0 ou à 1, le raisonnement est totalement inutilisable. L'argumentation mathématique est ici complètement sans objet et ne mène nulle part. Comme je l'ai dit précédemment, la seule manière pour un système axiomatique formel de produire ce genre de résultats, c'est essentiellement de les accepter comme des hypothèses ; ce qui signifie que vous ne raisonnez pas. Après tout, n'importe quoi peut être démontré si vous le considérez comme un postulat ajouté à votre ensemble d'axiomes. Il s'agit bien là du pire des scénarios ; l'information mathématique y est irréductible. C'est un cas où il n'y a aucune structure, aucune corrélation, aucun modèle que nous puissions percevoir.

4. Le hasard en arithmétique

Qu'en est-il du hasard en arithmétique dans tout ceci ? Revenons maintenant à Gödel (je l'avais évoqué un peu vite précédemment et à présent nous le retrouvons).

Turing a établi que l'on ne peut pas recourir à une démonstration pour décider si un programme s'arrêtera. On ne peut pas toujours prouver qu'un programme se terminera ou non. C'est de cette manière qu'il a détruit le rêve hilbertien d'une mathématique universelle. J'ai moi-même semé une confusion plus grande encore en examinant une autre sorte de question ; en l'occurrence, pouvons-nous prouver que le cinquième bit de ce nombre réel particulier qu'est

0 < Oméga = Somme p s'arrête 2 - |p| < 1

est 0 ou 1, ou bien que le huitième bit est 0 ou 1 ? Mais il s'agit là de questions un peu étranges. Qui avait jamais entendu parler du halting problem en 1936 ? Ce n'est pas là le genre de choses dont s'occupent habituellement les mathématiciens. Nous sommes embarrassés, certes, mais avec des questions qui sont assez éloignées des mathématiques usuelles.

Même si l'on ne peut pas obtenir un système axiomatique formel qui permette de toujours démontrer qu'un programme se termine ou non, un tel système pourrait s'avérer excellent pour tout le reste, et de cette manière, on pourrait parvenir à une version amendée du rêve de Hilbert. Il en est de même pour la probabilité d'arrêt Oméga. Si le halting problem semble un tout petit peu bizarre (et il le paraissait assurément en 1936), Oméga est quant à lui tout nouveau et il paraît certainement bizarre lui aussi. Qui a jamais entendu parler d'une probabilité d'arrêt ? Ce n'est pas le genre de choses que les mathématiciens créent normalement. Finalement, en quoi serai-je concerné par tous ces résultats d'incomplétude ?

Gödel avait déjà affronté cette question avec son assertion qui est vraie mais n'est pas démontrable. C'est une assertion qui dit d'elle-même qu'elle n'est pas prouvable ; mais de telles choses n'arrivent jamais dans les mathématiques réelles. L'un des éléments principaux de la preuve de Gödel est de réussir à construire une assertion arithmétique qui dit d'elle-même qu'elle n'est pas démontrable. C'est l'obtention d'une telle assertion auto-référentielle en arithmétique élémentaire qui exigeait tant d'ingéniosité.

De nombreux travaux ont été effectués à partir de la preuve de Gödel, et ceux-ci ont montré que les problèmes ayant trait à la calculabilité sont équivalents aux problèmes arithmétiques sur les nombres entiers. Plusieurs noms viennent à l'esprit. Julia Robinson, Hilary Putnam et Martin Davis ont réalisés des travaux parmi les plus importants et le résultat fondamental a été trouvé en 1970 par Youri Matiiassevitch. Il a construit une équation diophantienne, c'est-à-dire une équation algébrique qui met en oeuvre uniquement des nombres entiers et un certain nombre de variables. Une de ces variables, appelons-la K, joue le rôle d'un paramètre. C'est une équation polynomiale avec des coefficients entiers et toutes les inconnues doivent également être des nombres entiers ; voilà la définition d'une équation diophantienne. Comme je l'ai dit, l'une de ces inconnues est un paramètre, et l'équation de Matiiassevitch possède une solution pour une valeur particulière du paramètre K si et seulement si le Kième programme d'ordinateur s'arrête.

En 1900, Hilbert avait demandé s'il existe un algorithme qui permette de décider si une équation diophantienne quelconque - c'est-à-dire une équation algébrique qui utilise uniquement des nombres entiers - possède une solution. C'est le dixième problème dans sa fameuse liste des vingt-trois problèmes. Matiiassevitch a montré en 1970 que ce problème est équivalent à celui de décider si un programme quelconque s'arrête. Le halting problem de Turing est donc exactement aussi difficile que le dixième problème de Hilbert. Il est rigoureusement aussi difficile de décider si un programme quelconque s'arrêtera que de décider si une équation diophantienne quelconque possède une solution. Il n'existe par conséquent aucun algorithme qui permette de réaliser cela, et ainsi, le dixième problème de Hilbert ne peut pas être résolu ; tel est le résultat obtenu par Matiiassevitch en 1970 [7] .

Matiiassevitch a continué ensuite à travailler sur ce sujet. Il a notamment réalisé en 1984 un ensemble de travaux en collaboration avec James Jones. J'ai pu utiliser ces travaux pour marcher sur les traces de Gödel et suivre ainsi son exemple. J'ai montré, vous vous en souvenez, qu'il règne un hasard absolu et une totale absence de structure, qu'il n'existe aucun modèle et que le raisonnement est complètement impuissant lorsque l'on s'intéresse aux bits distincts du nombre suivant :

0 < Oméga = Somme p s'arrête 2 - |p| < 1

En suivant Gödel, convertissons cette expression en quelque chose qui se rapporte à la théorie élémentaire des nombres. On peut alors retrouver dans l'arithmétique les ennuis que nous avons évoqués ; or, cette théorie est une base, un soubassement. La théorie élémentaire des nombres (c'est-à-dire les nombres 1, 2, 3, 4, 5, etc., ainsi que l'addition et la multiplication) remonte en effet aux Grecs et constitue la partie la plus solide des mathématiques. Dans la théorie des ensembles, on s'intéresse à des objets étranges comme les grands cardinaux, tandis qu'en arithmétique élémentaire, on ne s'occupe même pas de dérivées ou d'intégrales mais seulement des nombres entiers. En utilisant le résultat obtenu par Matiiassevitch et Jones en 1984, j'ai pu véritablement habiller Oméga arithmétiquement et obtenir du hasard au sein de la théorie élémentaire des nombres.

Je suis parvenu à une équation diophantienne exponentielle possédant un paramètre. L'expression "équation diophantienne exponentielle" signifie simplement que les variables peuvent être des exposants. C'est une différence avec Matiiassevitch qui a montré que le dixième problème de Hilbert n'est pas résoluble en se servant d'équations diophantiennes polynomiales, ce qui signifie que les exposants y sont toujours des nombres entiers naturels constants. J'autorise quant à moi des expressions telles que XY. On ne sait pas encore si cela est véritablement nécessaire. Il se pourrait que l'on puisse arriver à un résultat similaire avec une équation diophantienne polynomiale. C'est une question ouverte ; je crois qu'elle n'a pas encore été réglée. Pour l'instant, j'ai obtenu une équation diophantienne exponentielle possédant dix-sept mille variables. Cette équation tient sur deux cent pages et une des variables est un paramètre.

Il s'agit d'une équation où chaque constante est un nombre entier naturel et où toutes les variables sont également des nombres naturels positifs (autrement dit, ce sont des entiers non-négatifs). L'une de ces variables est donc un paramètre, et l'on peut modifier la valeur de ce paramètre qui peut être égal à 1, 2, 3, 4, 5, etc. On se demande alors si cette équation possède un nombre fini ou infini de solutions. Mon équation est construite de telle manière qu'elle a un nombre fini de solutions si un bit particulier de Oméga vaut 0, et elle a un nombre infini de solutions si ce bit est égal à 1. Décider si, pour chacun des cas particuliers, cette équation diophantienne exponentielle possède un nombre fini ou infini de solutions est donc exactement identique à la détermination d'un bit spécifique de la probabilité d'arrêt :

0 < Oméga = Somme p s'arrête 2 - |p| < 1

L'équation obtenue est complètement insoluble parce que Oméga est une information mathématique irréductible.

Je vais maintenant souligner la différence entre ce résultat et celui de Matiiassevitch à propos du dixième problème de Hilbert. Matiiassevitch a montré qu'il existe une équation diophantienne polynomiale ayant un paramètre et possédant la particularité suivante : lorsque vous variez le paramètre et demandez si cette équation a une solution, cette question est équivalente au halting problem de Turing et échappe de ce fait au pouvoir du raisonnement mathématique, au raisonnement axiomatique formel.

En quoi ce résultat diffère-t-il du mien ? J'utilise une équation diophantienne exponentielle, ce qui signifie que les exposants variables y sont autorisés. Dans le travail de Matiiassevitch par contre, seuls les exposants constants sont admis. La grande différence réside néanmoins dans le fait que Hilbert réclamait un algorithme permettant de décider si une équation diophantienne possède une solution. La question que l'on doit se poser pour introduire le hasard dans la théorie élémentaire des nombres, dans l'arithmétique des nombres naturels, est un petit peu plus sophistiquée. Au lieu de se demander s'il existe une solution à ce problème, on s'interroge pour savoir s'il existe un nombre fini ou un nombre infini de solutions ; il s'agit d'une question plus abstraite et cette différence est nécessaire.

J'ai construit cette équation de deux cent pages de telle façon qu'elle possède un nombre fini ou un nombre infini de solutions en fonction de la valeur 0 ou 1 d'un certain bit de la probabilité d'arrêt Oméga. Lorsque l'on varie le paramètre de cette équation, on obtient chacun des bits de Oméga. L'équation de Matiiassevitch est construite de telle sorte qu'elle possède une solution si et seulement si un programme particulier s'arrête. Et lorsque l'on varie le paramètre de l'équation de Matiiassevitch, on obtient tous les programmes d'ordinateurs.

La perte complète de structure du nombre Oméga, l'information mathématique aléatoire et irréductible de ce nombre se retrouvent donc jusque dans l'arithmétique. Le raisonnement est totalement sans pouvoir dans ces régions de l'arithmétique. L'équation en question le montre. Comme je viens de le dire, j'ai utilisé pour obtenir cette équation des idées qui remontent à l'article original de Gödel (1931). Mais c'est le travail de Jones et Matiiassevitch publié en 1984 qui m'a finalement fournit les outils dont j'avais besoin.

Voilà donc pourquoi j'affirme qu'il y a du hasard dans la théorie élémentaire des nombres. Nous sommes là en présence d'un mur de pierres impénétrable et il s'agit bien encore une fois du pire des scénarios. Nous savions depuis Gödel que nous ne pouvions pas parvenir à un système axiomatique formel qui soit complet. Nous savions que nous aurions des soucis et Turing nous a montré combien cela était fondamental ; Oméga est cependant un cas extrême où le raisonnement échoue complètement.

Sans donner d'autres détails, je vais conclure en utilisant de manière non formelle le vocabulaire de la théorie algorithmique de l'information. L'équation de Matiiassevitch fournit N questions arithmétiques qui possèdent une réponse de type oui/non et produit seulement log N bits d'information algorithmique. Ma propre équation conduit à N questions arithmétiques qui possèdent également une réponse de type oui/non ; elle génère par contre une information mathématique irréductible et incompressible.

5. Les mathématiques expérimentales

Voyons dans les quelques minutes qui nous restent ce que signifient toutes ces idées.

Examinons en premier lieu quelle relation ces conceptions entretiennent avec la physique. Lorsque la mécanique quantique s'est développée, elle a provoqué une grande controverse en raison de son caractère non déterministe. Einstein n'aimait pas cette idée et déclarait que << dieu ne joue pas aux dés !>>. Mais, comme je suis sûr que vous le savez tous, nous comprenons maintenant grâce à la théorie du chaos et à la dynamique non linéaire que le hasard et l'imprévisibilité existent au sein même de la physique classique. Mon travail s'inscrit dans cette tendance et montre que les mathématiques pures - et, en réalité, même la théorie élémentaire des nombres, c'est-à-dire l'arithmétique des nombres naturels 1, 2, 3, 4, 5, etc. - sont sur le même bateau. Il existe également du hasard en ce domaine. Comme un journal pourrait en faire son titre, non seulement Dieu joue aux dés en mécanique quantique et en physique classique, mais il y joue également en mathématiques pures, et même dans la théorie élémentaire des nombres. Si un nouveau paradigme est bien en train d'émerger, le hasard est au coeur de celui-ci. Dans le même ordre d'idée, le hasard est aussi au coeur de la théorie quantique du champ, ainsi que l'ont montré très clairement les particules virtuelles et les intégrales sur un chemin (c'est-à-dire, les sommes sur toutes les histoires) que l'on doit à Feynman. Mon travail s'accorde donc bien avec nombre de travaux en physique, et c'est pour cela que je suis souvent invité à parler dans des congrès sur les sciences physiques.

La question importante, cependant, ne concerne pas la physique mais les mathématiques. J'ai entendu dire que Gödel avait écrit une lettre à sa mère qui était restée en Europe. Vous savez que Gödel et Einstein étaient amis à l'Institute for Advanced Study et l'on pouvait les voir à cette époque se promener ensemble. Gödel, donc, avait apparemment écrit une lettre à sa mère où il disait regretter que son propre travail n'avait pas sur les mathématiciens le même effet que l'impact véritablement considérable du travail d'Einstein sur les physiciens. Son oeuvre n'a pas de conséquence sur la manière dont les mathématiciens abordent leur travail quotidien. Je pense qu'il s'agit là de la bonne question : comment devrions-nous réellement faire des mathématiques ?

J'ai affirmé que mon résultat sur l'incomplétude est beaucoup plus fort que celui de Gödel. S'il en est ainsi, la question de savoir si les mathématiques doivent être pratiquées à la manière habituelle paraîtra plus claire. Mais en quoi consiste la manière ordinaire de "faire des mathématiques" ? En dépit du fait que chacun sache que tout système fini d'axiomes est incomplet, comment les mathématiciens travaillent-ils à l'heure actuelle ? Imaginons une conjecture à laquelle vous réfléchissez depuis plusieurs semaines ; vous croyez qu'elle est vraie parce que vous l'avez testé sur de très nombreux cas à l'aide d'un ordinateur. Peut-être est-ce une conjecture sur les nombres premiers que vous essayez de démontrer depuis deux semaines. Toutefois, vous ne pouvez pas dire après ces deux semaines : << mais bien sûr ! je n'arrive pas à prouver cette conjecture à cause du théorème d'incomplétude de gödel ! il suffit que je la considère comme un nouvel axiome>>. Et pourtant, on devrait procéder ainsi si l'on prenait au sérieux le théorème d'incomplétude de Gödel. Les mathématiciens sourient, mais les physiciens agissent en fait de cette manière.

Examinons l'histoire de la physique que l'on peut faire débuter avec la physique newtonienne. On ne peut pas dériver les équations de Maxwell de la physique newtonienne. Il s'agit d'un nouveau domaine d'expérience qui exige de nouveaux postulats. Il en est de même pour la relativité restreinte bien que celle-ci soit presque contenue dans les équations de Maxwell. Et la situation est identique pour l'équation de Schrödinger que l'on ne peut dériver de la physique newtonienne ou des équations de Maxwell. C'est également un nouveau domaine d'expérience qui exige de la même façon de nouveaux axiomes. Les physiciens sont donc habitués à l'idée suivante : lorsque l'on commence à expérimenter à une échelle plus petite, ou lorsque l'on aborde de nouveaux phénomènes, on peut avoir besoin de nouveaux principes pour comprendre et expliquer ce qui se passe.

En dépit des résultats sur l'incomplétude, les mathématiciens ne se comportent pas du tout comme les physiciens. Il admettent encore, à un niveau subconscient, que le petit nombre de principes et de postulats ainsi que les quelques schémas d'inférence qu'ils ont appris lorsqu'ils étaient étudiants sont suffisants. Ils croient au plus profond d'eux-mêmes que si vous ne pouvez pas démontrer un résultat, c'est votre faute. Il s'agit là probablement d'une bonne attitude, meilleure en tout cas que de blâmer quelqu'un d'autre. Mais examinons de ce point de vue un problème comme l'hypothèse de Riemann. Un physicien affirmerait qu'il existe une très grande évidence expérimentale en faveur de l'hypothèse de Riemann et irait de l'avant en considérant celle-ci comme une conjecture de travail.

Qu'est-ce que l'hypothèse de Riemann ? De nombreuses questions non résolues ayant trait à la distribution des nombres premiers pourraient être décidées si l'on admettait cette hypothèse. On a utilisé des ordinateurs pour vérifier ces différentes conjectures et elles marchent admirablement bien. Ce sont des formules élégantes mais personne n'est en mesure de les démontrer. Un grand nombre d'entre elles découlent de l'hypothèse de Riemann et ce seul fait serait suffisant pour un physicien : l'hypothèse est utile et explique un grand nombre de choses. Toutefois, un physicien serait prêt à reconnaître bien sûr qu'il a commis une gaffe si un fait d'expérience venait ultérieurement contredire sa théorie. Cela arrive très souvent.

On abandonne constamment des théories en physique des particules et la plupart d'entre elles disparaissent rapidement. Les mathématiciens par contre n'aiment pas revenir en arrière. Mais si l'on considère cette question honnêtement, on doit y perdre à procéder ainsi.

Je pense que ma conclusion devrait maintenant être évidente. Je crois que la théorie élémentaire des nombres ainsi que toutes les mathématiques devraient être davantage pratiquées dans l'esprit des sciences expérimentales, et que l'on devrait être prêt à adopter de nouveaux principes. J'estime que la proposition d'Euclide selon laquelle un axiome est une vérité en-soi est une grave erreur. L'équation de Schrödinger n'est sûrement pas une vérité évidente en-soi ! Et l'hypothèse de Riemann n'est pas évidente non plus, mais elle est par contre très utile.

Je crois donc que les mathématiciens ne devraient pas ignorer l'incomplétude. Méconnaître celle-ci semble être une sage mesure, mais nous fait perdre certains résultats auxquels nous pourrions accéder. C'est comme si les physiciens déclaraient qu'ils ne veulent ni de l'équation de Schrödinger, ni des équations de Maxwell, et qu'ils adhéraient à la conception newtonienne au point que tout devrait être déduit des lois de Newton (Maxwell avait tenté cela et il avait même obtenu un modèle mécanique du champ électromagnétique. On n'enseigne plus heureusement ce genre de chose au collège !).

J'ai proposé ce genre d'idées il y a maintenant vingt ans quand je parvenais à mes premiers résultats sur l'incomplétude en utilisant la théorie de l'information. Mais indépendamment de mon cheminement, une nouvelle école de philosophie des mathématiques est apparue ; c'est une école de pensée "quasi-empiriste" à l'égard des fondements des mathématiques et elle est bien représentée par la compilation de Thomas Tymoczko New Directions in the Philosophy of Mathematics (Boston : Birkhäuser, 1986). Il s'agit d'un excellent recueil d'articles. Le livre de John Casti Searching for Certainty (New York : Morrow, 1990) constitue une autre référence et possède un bon chapitre sur les mathématiques. La dernière partie de ce chapitre traite d'ailleurs du point de vue quasi-empiriste. On peut citer enfin Imre Lakatos qui était l'un des auteurs impliqué dans ce nouveau mouvement ; il avait quitté la Hongrie et travaillait à Cambridge à cette époque là  [8] .

Au début du siècle, les trois écoles principales en philosophie des mathématiques étaient celle de Russell et Whitehead selon laquelle la logique est le fondement de toutes les mathématiques, l'école formaliste de Hilbert et enfin l'école "intuitionniste" et constructiviste de Brouwer. Certains estiment que Hilbert croyait que les mathématiques sont un jeu sans signification mettant en oeuvre des marques d'encre sur le papier. Pas du tout ! Il disait simplement que pour que les mathématiques soient absolument claires et précises, on doit spécifier les règles qui puissent permettre de déterminer si une preuve est correcte de façon si rigoureuse qu'elles deviennent mécaniques. Quiconque aurait pensé que les mathématiques sont sans signification aurait dû être très énergique, déployer un travail considérable et être un leader d'une immense influence.

À l'origine, la plupart des mathématiciens ont soutenu Hilbert. Même après que le travail de Gödel et de manière encore plus catégorique celui de Turing eurent montré que le rêve de Hilbert ne marchait pas, les mathématiciens continuèrent en pratique comme auparavant, dans l'esprit de Hilbert. L'attitude constructiviste de Brouwer était considéré la plupart du temps comme un fléau, et Russell et Whitehead faisaient face à de nombreux problèmes en tentant de retrouver toutes les mathématiques à partir de la logique. Si l'on dérive les mathématiques de la théorie des ensembles, on découvre alors qu'il est attrayant de définir les nombres en termes d'ensembles (von Neumann avait travaillé en ce sens). Mais on rencontre de nombreux problèmes avec les ensembles et les nombres entiers ne deviennent pas plus sûrs lorsqu'ils sont basés sur quelque chose qui s'avère encore plus problématique.

À l'heure actuelle, tout est sens dessus dessous. Pas à cause d'un quelconque argument philosophique, des théorèmes de Gödel, de Turing ou de mes propres résultats sur l'incomplétude. Tout est devenu sens dessus dessous pour une raison très simple : l'avènement de l'ordinateur.

Comme chacun sait, l'ordinateur a modifié la façon dont on accomplit chaque chose. L'ordinateur a ainsi considérablement et amplement accru l'expérience mathématique. Il est en effet devenu très facile d'effectuer des calculs, de tester de nombreux cas, de réaliser des expériences à l'aide d'ordinateurs. L'ordinateur a tellement augmenté le champ de l'expérience mathématique que pour s'en sortir, on est obligé de procéder de manière plus pragmatique. Les mathématiciens agissent effectivement de façon plus pragmatique et davantage à la façon des scientifiques des disciplines expérimentales. Cette tendance nouvelle est souvent appelée "mathématiques expérimentales" et cette expression provient pour beaucoup du champ des recherches sur le chaos, les fractales et la dynamique non linéaire.

Il arrive souvent lorsque l'on effectue des expérimentations avec un ordinateur, c'est-à-dire des expérimentations numériques avec des équations, que l'on s'aperçoive qu'il se passe quelque chose et l'on formule alors une conjecture. C'est sans aucun doute agréable si vous pouvez démontrer celle-ci, et tout particulièrement si la preuve est courte. Je ne suis pas sûr en effet qu'une démonstration d'un millier de pages nous aide beaucoup. Mais posséder une preuve courte est certainement mieux que de ne pas avoir de démonstration. Et si l'on obtient plusieurs preuves à partir de différents points de vue, c'est excellent.

Mais parfois, on ne peut pas trouver de démonstration et l'on ne peut pas attendre que quelqu'un d'autre en découvre une ; on doit alors poursuivre du mieux que l'on peut. Ainsi donc, actuellement, les mathématiciens vont quelquefois de l'avant en travaillant avec des hypothèses qui proviennent de résultats d'expérimentations sur ordinateur. Si les protagonistes de ces expérimentations sur ordinateur étaient physiciens, tout irait bien entendu pour le mieux ; les physiciens comptent toujours massivement sur l'expérience. Mais maintenant, même les mathématiciens procèdent parfois ainsi. Je crois qu'il existe un nouveau journal intitulé Journal of Experimental Mathematics [9] . Ils auraient dû me prendre dans leur comité éditorial car j'ai proposé cette conception depuis une vingtaine d'années en me basant sur les idées de la théorie algorithmique de l'information.

Pour terminer, ce n'est donc ni Gödel, ni Turing, ni mes propres résultats qui ont conduit les mathématiques dans une direction expérimentale, une orientation quasi-empirique. La raison pour laquelle les mathématiciens ont changé leurs habitudes de travail s'appelle l'ordinateur. C'est, je pense, une excellente plaisanterie ! Il est également amusant de constater que des trois anciennes écoles de philosophie mathématique - logiciste, formaliste et intuitionniste -, la plus négligée ait été celle de Brouwer qui avait défendu une attitude constructiviste bien des années avant que l'ordinateur ne donne une impulsion fantastique au constructivisme.

Mais le simple fait que tout le monde fasse quelque chose ne signifie pas bien sûr que cette attitude soit justifiée. Le changement dans la façon dont les mathématiciens se comportent ne provient pas du théorème de Gödel, de celui de Turing ou de mes propres théorèmes, mais de l'ordinateur. Je pense cependant que la suite de travaux que je viens de retracer fournit une justification théorique à ce que tout le monde accomplit sans soucis d'une telle explication. Et je pense aussi que la question de savoir comment l'on devrait actuellement faire des mathématiques requiert au moins le travail d'une autre génération. C'est fondamentalement ce que je voulais dire, et je vous remercie pour votre attention.

Bibliographie

1. G. J. Chaitin : Information-Theoretic Incompletness. World Scientific, 1992.
2. G. J. Chaitin : Information, Randomness & Incompletness. Second edition. World Scientific, 1990.
3. G. J. Chaitin : Algorithmic Information Theory. Revised third printing. Cambridge University Press, 1990.


Notes

[1] Randomness in Arithmetic and the Decline & Fall of Reductionism in Pure Mathematics. Traduit de l'anglais (USA) par Patrick Peccatte. Article repris dans The Limits of Mathematics (April 28, 1997). 
Cette traduction est également disponible sur le site Web de Chaitin .

[2] [N.D.T. L'article original de Gödel est traduit en français. Cf. Ernst Nagel, James R. Newman, Kurt Gödel, Jean-Yves Girard : Le théorème de Gödel. Traductions de l'anglais et de l'allemand par Jean-Baptiste Scherrer. Paris : éditions du Seuil, 1989. pp. 105-143].

[3] [N.D.T. En français dans le texte].

[4] [N.D.T. L'expression halting problem est suffisamment consacrée pour que nous évitions de la traduire par la suite].

[5] [N.D.T. L'article original de Turing est traduit en français. Cf. Alan Turing, Jean-Yves Girard : La machine de Turing. Traduction de l'anglais par Julien Basch et Patrice Blanchard. Paris : éditions du Seuil, 1995. pp. 47-104].

[6] - Note technique : Il est préférable actuellement de concevoir la complexité d'un système axiomatique formel comme la longueur en bits du programme qui énumère l'ensemble de tous les théorèmes.

[7] [N.D.T. Cf. Youri Matiiassevitch : Le dixième problème de Hilbert. Son indécidabilité. Traduit par Patrick Cegielski et Denis Richard. Revu et corrigé par l'auteur. Paris : Masson, 1995] 

[8] [N.D.T. Lakatos est décédé en 1974. L'anthologie de Thomas Tymoczko reprend deux de ses articles : A Renaissance of Empiricism in the Recent Philosophy of Mathematics ? (pp. 29-48) et What Does Mathematical Proof Prove ? (pp. 153-162).
En français, cf. l'essai : Imre Lakatos : Preuves et réfutations. Essai sur la logique de la découverte mathématique. Paris : Hermann, 1984. Traduction française par N. Balacheff et J. M. Laborde de Proofs and Refutations. The logic of mathematical discovery. 1976. Cambridge University Press.]

[9] [N.D.T. Cf. Journal of Experimental Mathematics .
Voir également le site Center for Experimental and Constructive Mathematics (C.E.C.M.) .
Et l'article Experimental mathematics : A discussion par J. Borwein, P. Borwein, R. Girgensohn, et S. Parnes.]


Histoire et philosophie des mathématiques
Le quasi-empirisme en philosophie des mathématiques. Une présentation
Liens mathématiques en relation indirecte avec le quasi-empirisme
Retour à la page d'accueil