David Madore's WebLog: Qui peut dire le nombre le plus grand ?

Première partie : des nombres « constructifs »

Le nombre 10↑100 (c'est-à-dire 10 puissance 100, j'évite les exposants parce que ça devient vite encombrant) a été baptisé go(o?)gol par le neveu d'un mathématicien facétieux (avant le moteur de recherche et sans aucun rapport avec l'écrivain russe) ; le nombre 10↑(10↑100), c'est-à-dire un 1 suivi d'un googol de zéros, est déjà plus respectable : on ne peut pas l'écrire complètement sur papier en décimal parce qu'il y a moins d'atomes dans l'univers observable qu'il n'y a de zéros à écrire. On peut alors continuer avec 10↑(10↑(10↑100)) (un gogolplexplex, ou un 1 suivi d'un gogolplex de zéros), puis considérer 10↑(10↑(10↑…(10↑10)…)) avec 100 fois le nombre 10, ce que Knuth propose de noter 10↑↑100, puis on peut considérer 10↑↑(10↑↑(10↑↑…(10↑↑10)…)) avec 100 fois le nombre 10 et noter ça 10↑↑↑100, puis on peut considérer 10↑⋯↑100 avec 100 flèches, ou bien avec ce nombre-là de flèches, ou avec ce-nombre-là, ou en répétant 100 fois l'opération (là on a en gros fait la construction du nombre de Graham, expliqué ici pour les non-mathématiciens).

Bon, mais si on veut faire les choses de façon un peu systématique ? On ne peut pas ne pas avoir remarqué que ces constructions rappellent un peu la manière dont les ordinaux fonctionnent (pour décrire l'ordinal ε₀, j'empile des puissances de ω, ensuite on peut s'amuser à empiler des ε en indice ou des choses comme ça). Et de fait, il y a un rapport. Ou en fait, ce qui est peut-être confusant, il y a deux rapports : il y a deux façons assez standard de fabriquer de grands nombres entiers à partir d'un ordinal grand-mais-pas-trop, ce sont la hiérarchie à croissance lente et la hiérarchie à croissance rapide (chacune de ces deux hiérarchies admet de petites variations de détails dans sa définition, et par ailleurs de terminologie : on parle aussi de hiérarchie de Grzegorczyk pour la seconde). Dans les deux cas, on construit pour chaque ordinal (+ une donnée que je ne détaille pas pour l'instant) non pas un grand entier mais une fonction (des entiers vers les entiers) qui croît très vite ; on peut ensuite appliquer cette fonction à un nombre n modérément grand (pour fixer les idées, disons, 1000) pour obtenir un nombre qui, lui, est très grand. Sans rentrer dans les détails, disons que la hiérarchie à croissance lente correspond, très grossièrement, à substituer n à ω dans l'expression de l'ordinal, ce qui doit évidemment se définir avec soin pour les choses comme ε₀ (par exemple, la valeur en n=1000 de la fonction associée à l'ordinal ω↑ω de la hiérarchie à croissance lente vaut 1000↑1000, soit 10↑3000 ; et pour l'ordinal ε₀ cela donne 1000↑↑1000). La hiérarchie à croissance rapide, elle, consiste à chaque nouvelle étape à itérer la fonction précédente, donc elle grandit énormément plus vite : les fonctions de cette hiérarchie indicées par les entiers naturels correspondent en gros aux tranches de la fonction d'Ackermann, celle indicée par ω est en gros la diagonale de la fonction d'Ackermann et n'est déjà plus primitive récursive, puis on va itérer cette fonction-là, etc. Néanmoins, on peut toujours trouver plus d'ordinaux qu'on en veut, et à tout indice dans la hiérarchie à croissance rapide il existe un indice (beaucoup plus loin) dans la hiérarchie à croissante lente qui finit par dominer la fonction correspondante (par exemple, en gros, à 3 on peut ainsi associer ε₀ ; à ω+1 on va associer l'ordinal de Feferman-Schütte ; à ω·2 et ω·2+1 on va associer le petit et le grand ordinaux de Veblen ; et à ε₀ on va associer l'ordinal de Bachmann-Howard). Il y a donc, fatalement, un — et une infinité — d'ordinaux pour lesquels la hiérarchie à croissance lente et la hiérarchie à croissance rapide coïncident (en « ordre de grandeur », un terme que je ne chercherai pas à rendre précis). Le plus petit d'entre eux est celui que j'appelle l'ordinal de Takeuti-Feferman-Buchholz (mais je suis le seul à utiliser ce nom). [Ajout : cf. cette entrée ultérieure pour des descriptions plus précises de ces ordinaux.]

Bref, pour définir des grands nombres, on peut chercher à définir des grands ordinaux. Le nombre de Graham mentionné ci-dessus, par exemple, est comparable aux petites valeurs de la fonction indicée par ω+1 dans la hiérarchie à croissante rapide (ou, comme je l'ai mentionné, par l'ordinal de Feferman-Schütte dans la hiérarchie à croissance lente). La fonction TREE de Friedman qui découle du théorème de plongement de Kruskal est en quelque part entre les fonctions de la hiérarchie à croissance rapide indicées par l'ordinal de Feferman-Schütte et le petit ordinal de Veblen ; une fonction analogue pour le théorème de Robertson-Seymour est en gros majorée par le premier niveau où les hiérarchies à croissances rapide et lente se retrouvent (indicé par l'ordinal de Takeuti-Feferman-Buchholz). La valeur en 1000 de cette fonction est tellement colossale que ça devient vraiment long et fastidieux d'en faire une définition formelle (mais je vais revenir sur les règles).

À ce niveau-là, on peut donc commencer à se demander quels sont les plus grands ordinaux qui aient jamais été définis. Sauf qu'il ne s'agit pas de n'importe quels ordinaux : les hiérarchies de fonctions évoquées ci-dessus n'ont de sens que pour un ordinal constructif muni de suites fondamentales, c'est-à-dire, en gros, qu'on doit se donner une façon constructive (i.e., calculable) de représenter les ordinaux plus petits et d'atteindre n'importe quel ordinal jusque là par une suite standard d'ordinaux plus petits. On parle de système de notations ordinales pour définir ces choses-là. Ce qui est assez étonnant (voir ici pour une introduction à ce sujet), c'est que la définition de ces très grands ordinaux passe par des ordinaux encore plus grands, un peu de la manière dont on est en train de se servir d'ordinaux infinis pour définir des grands entiers naturels. Il y a quelque chose d'assez mystérieux dans toute cette histoire. Disons qu'on a plusieurs niveaux :

0. les grands entiers naturels (i.e., les ordinaux <ω),
1. les grands ordinaux constructifs (i.e., les ordinaux <ω₁^CK),
2. les grands ordinaux dénombrables [dans l'univers constructible] (i.e., les ordinaux <ω₁^L),
3. les grands cardinaux [qui ont le droit d'exister dans l'univers constructible],

(je parlerai dans une autre entrée de ce que signifie l'univers constructible)

où chaque niveau se « reflète » en partie dans le niveau précédent, d'une manière pas complètement bien comprise (et pas évidente à formaliser). Par exemple, le cardinal ℵ_ω a un analogue dénombrable noté ω_ω^CK, qui a à son tour un « écrasement » constructif que j'ai appelé ordinal de Takeuti-Feferman-Buchholz (le premier où les hiérarchies à croissances lente et rapide coïncident en gros), et ceci définit une fonction dans la hiérarchie à croissance lente ou rapide dont la valeur en — disons — 1000 définit un entier naturel très grand (qui donne une borne sur des problèmes de graphes dérivés du théorème de Robertson-Seymour comme je l'ai signalé). Le grand cardinal appelé premier cardinal [faiblement] inaccessible (à supposer qu'il existe…) a un analogue dénombrable appelé le premier ordinal récursivement inaccessible, qui a à son tour un « écrasement » constructif (l'écrasement d'un inaccessible, ou ordinal de preuve de KP enrichi de l'axiome tout ensemble est élément d'un ensemble admissible), et ceci définit une fonction dans la hiérarchie à croissance lente ou rapide dont la valeur en 1000 définit un entier naturel. Très grand. Vraiment très très grand. Mais fini. De même, on peut partir d'un cardinal Mahlo et obtenir un nombre encore beaucoup plus grand.

Quel est le plus grand qu'on sache fabriquer par ce genre de technique ? À ma connaissance, l'état de l'art des notations ordinales est décrit par la thèse de Jan-Carl Stegert (Ordinal proof theory of Kripke-Platek set theory augmented by strong reflection principles (2010), disponible ici en PDF) où le grand cardinal de départ est quelque chose comme le plus petit κ qui soit (<κ)-indescriptible (voir la définition 12.2.1 page 101 de la thèse pour les détails, où le cardinal en question est noté ϒ). La description du système de notations ordinales qui définit un ordinal constructif (l'ordinal de preuve de la théorie Stability qui enrichit KPi par l'existence de toutes sortes de plongements élémentaires) est très complexe. Il y a quelqu'un sur le Web qui prétend avoir un système de notations beaucoup plus puissant, mais je soupçonne qu'il se trompe, même si n'étant pas expert et n'ayant pas étudié en détail son système je ne peux pas l'affirmer avec certitude. Toujours est-il que l'un ou l'autre système doit permettre de définir des très grands entiers : les plus grands qu'on sache décrire de façon complètement « explicite » et « constructive ».

Deuxième partie : quelles sont les règles ?

Mais à ce moment-là il faut se demander quelles sont exactement les règles du jeu : qu'est-ce que cela signifie que de définir un entier, ou surtout, de le définir explicitement ?

Le petit malin est certainement tenté de définir :

Le plus grand entier qui peut se définir en moins de 10↑1000 symboles.

L'idée étant que ce nombre sera forcément plus grand que tous ceux que j'ai définis avant, puisque ces derniers ont des définitions qui ont été publiées et que ces définitions (par exemple la thèse de Stegert + la définition de la hiérarchie à croissance lente) ne font certainement pas plus que 10↑1000 symboles. L'ennui est que la définition ci-dessus est contradictoire vu qu'elle tient en moins de 10↑1000 symboles (et si on ajoute « plus un » à la fin, ça tient toujours en moins de 10↑1000 symboles) : le paradoxe vient de ce que pour définir formellement définissable en, il faut un cadre formel strictement plus puissant que celui dans lequel on parle de définir. Par exemple, si j'interprète se définir comme être définissable dans le langage de la théorie des ensembles, la définition n'a pas de sens dans le langage de la théorie des ensembles puisque la vérité est indéfinissable (cf. une entrée précédente pour plus de détails). Et si on n'est que modérément platoniste comme je le suis, on peut trouver que ce nombre n'a même pas vraiment de sens (parce qu'il préjuge d'un univers de la théorie des ensembles, sa valeur pouvant dépendre fortement de l'univers en question, et rien ne dit qu'il y ait un univers « naturel »).

Reculons d'un cran, donc. On peut considérer la définition suivante :

Le plus grand entier qui peut être calculé par un programme (dans le langage FlooP) qui peut s'écrire en moins de 10↑1000 symboles [ou : par une machine de Turing utilisant moins de 10↑1000 états].

(Ce genre de définitions s'appelle la fonction du castor affairé. Ou, si on préfère, on demande le plus grand nombre dont la complexité de Kolmogorov soit ≤10↑1000.) Ce nombre est mathématiquement parfaitement bien défini (une fois choisie une formalisation de machine de Turing, ou une description parfaitement précise du langage FlooP), et il est colossalement plus grand que ceux que j'ai pu fabriquer dans la première partie parce que ceux-ci pouvaient effectivement s'implémenter en langage FlooP en un nombre de symboles pas gigantesque (d'ailleurs, j'ai effectivement écrit du code Haskell qui, en principe, implémente les ordinaux jusqu'à celui de Takeuti-Feferman-Buchholz, et peut calculer la hiérarchie à croissance lente, et mon code fait 12ko : ce serait sans doute plus long en FlooP, mais pas des millions de fois plus long). Néanmoins, ce nombre, quoique mathématiquement bien défini, n'est pas facilement calculable par une machine de Turing, précisément parce que sa définition l'interdit (on peut bien essayer de lancer en parallèle l'exécution de toutes les machines de Turing de moins de 10↑1000 états, ce n'est pas très dur et ça demandera d'ailleurs beaucoup moins que 10↑1000 états à écrire, mais on ne saura jamais à coup sûr si certaines vont finir par s'arrêter en ayant produit un nombre gigantesque, ou continueront à tourner indéfiniment : pour cela, il faudrait accès à l'oracle de l'arrêt ; évidemment, si on accumule les oracles d'arrêt, on peut définir des nombres beaucoup plus grands : par exemple, pour ω niveaux d'oracle d'arrêt on a l'équivalent du plus grand entier qui peut se définir en moins de 10↑1000 symboles dans le langage de l'arithmétique, cette définition ayant bien un sens dans le langage de la théorie des ensembles car la vérité des énoncés arithmétiques est définissable, de nouveau cf. une entrée précédente ; et en fabriquant de grands ordinaux on peut de nouveau essayer de jouer à faire des grands nombres comme ça, qui sont nettement plus grands que les précédents parce qu'on a court-circuité la demande d'être effectivement calculables).

Notons que si au lieu du langage FlooP dans la définition j'avais utilisé le langage BlooP (décrit sur la même page Wikipédia), qui ne permet de fabriquer que des fonctions primitives récursives, le nombre obtenu serait tout à fait calculable et, quoique très grand, beaucoup plus petit, et d'ailleurs petit par rapport à la plupart de ceux de la première partie (puisque de l'ordre de la valeur en 10↑1000 de la fonction indicée ω dans la hiérarchie à croissance rapide).

Mais reculons de nouveau d'un cran : je veux maintenant un nombre calculable par une machine de Turing (qu'on pourrait énumérer en un temps pas totalement délirant), mais aussi grand que possible. Que faire ? Voici une astuce :

Le plus grand entier qui peut être calculé par un programme (dans le langage FlooP) [ou : par une machine de Turing] dont la bonne terminaison peut se démontrer dans ZFC en moins de 10↑1000 symboles.

[Ajout : j'ai écrit une entrée ultérieure pour parler de ce nombre plus en détails.]

Remarquez que c'est très différent du plus grand entier qui peut être défini dans le langage de la théorie des ensembles en moins de 10↑1000 symboles considéré plus haut : c'est beaucoup plus petit, et cette fois-ci le nombre est non seulement parfaitement bien défini, mais aussi explicitement calculable (comme demandé) : en effet, je peux écrire un programme qui va énumérer toutes les suites possibles de 10↑1000 symboles, vérifier s'il s'agit d'une preuve de terminaison dans ZFC d'une machine de Turing explicite (si on a formalisé tous ces concepts, ce n'est pas difficile) et, si c'est le cas, exécuter la machine correspondante (qui termine, puisqu'on en a une preuve !), regarder le nombre ainsi calculé, et prendre le maximum de tous. Tout ceci prend largement moins de 10↑1000 états d'une machine de Turing ou 10↑1000 symboles en langage FlooP. En revanche, le nombre ci-dessus est largement plus grand que tout ce que j'ai pu faire dans la première partie parce que ceux-ci s'implémentent bien sur des machines de Turing dont la preuve de terminaison peut se donner dans ZFC [même pour ceux qui utilisent des grands cardinaux, c'est un chouïa subtil ; en fait, l'arithmétique du second ordre suffit toujours] et n'est pas démesurément longue.

Remarque : ce qui rappellera peut-être à quel point les nombres envisagés sont gigantesques, le temps passé dans cette exécution à écrire les quelque chose comme 10↑(10↑1000) suites de 10↑1000 symboles pour y rechercher des démonstrations dans ZFC, est complètement négligeable par rapport au temps passé à exécuter la machine de Turing dont on aura trouvé une preuve d'exécution et qui produira le nombre le plus grand (parce que ce nombre est colossalement plus grand que 10↑(10↑1000)).

Ah, mais pour prouver le fait que ce programme s'arrête (celui qui calcule le nombre ci-dessus), j'ai utilisé plus que ZFC, j'ai utilisé le fait que si ZFC démontre qu'une machine de Turing s'arrête, alors elle s'arrête vraiment, ce qu'on appelle la Σ₁-véracité-arithmétique de ZFC, qui est plus fort que ZFC parce que ça en montre la consistance. (Bon, si c'est vrai, ZFC démontre quand même que la machine s'arrête, puisque, de fait, elle s'arrête, donc il suffit de donner une trace d'exécution complète, mais cette démonstration prend beaucoup plus que 10↑1000 symboles, elle en prend un nombre de l'ordre du nombre ci-dessus et on ne veut vraiment pas la donner explicitement. — Correction (2014-06-14) : en fait, non, la démonstration en question est certes plus longue que 10↑1000 symboles, mais pas beaucoup plus longue, parce que le lemme de réflexion de Lévy montre pour tout N explicite donné, de façon non uniforme en N, que le sous-système de ZFC où l'axiome de réflexion a été limité aux formules ayant au plus N alternations de quantificateurs [a un modèle transitif, donc] est arithmétiquement vrai, et cette démonstration prend une longueur polynomiale en N.)

En revanche, si je considère le nombre suivant :

Le plus grand entier qui peut être calculé par un programme (dans le langage FlooP) [ou : par une machine de Turing] dont la bonne terminaison peut se démontrer dans ZC+KP (c'est-à-dire ZFC où l'axiome du remplacement a été limité aux énoncés Δ₀) en moins de 10↑1000 symboles.

(J'ai pris ZC+KP comme système de référence parce que c'est un système assez standard, et raisonnablement fort, dont ZFC prouve la consistance et la Σ₁-véracité-arithmétique ; un modèle en est donné par les ensembles dont le cardinal est hériditairement inférieur au premier point fixe de la fonction beth.)

Cette fois je peux fournir non seulement une machine de Turing qui calcule ce nombre mais aussi une preuve dans ZFC que cette machine termine (aucune des deux n'étant démesurément longue), et ce nombre continue à écraser tous les nombres définis dans la première partie. On a toujours envie de dire qu'il n'est pas défini de façon vraiment constructive : l'ennui, c'est que cette fois-ci on ne sait pas précisément dire pourquoi, ni quelle règle il faudrait invoquer pour dire que c'est de la triche alors que les nombres de la première partie sont bien définis.

(En revanche, si j'affaiblis considérablement le système ZC+KP dans la définition ci-dessus, je finis par retomber en-dessous des définitions constructives de la première partie : par exemple, si je prends l'arithmétique de Peano du premier ordre, le nombre ainsi défini sera en gros la valeur en 10↑1000 de la fonction associée à ε₀ dans la hiérarchie à croissance rapide — ou à l'ordinal de Bachmann-Howard dans celle à croissance lente.)

(En guise de conclusion)

En guise de conclusion, on peut légitimement se poser la question philosophique de savoir si ces nombres ont un sens. Par exemple, est-ce que cela a vraiment un sens de se demander ce que sera l'état de l'Univers dans 10↑↑↑↑↑1000 années, pour ne pas dire le nombre de Graham ou ‹la valeur en 1000 de la fonction dans la hiérarchie à croissance lente associée à l'écrasement du premier cardinal inaccessible› ? Ou, si l'Univers est infini dans l'espace, qu'y a-t-il à un tel nombre d'années-lumières d'ici ? Est-ce que les religions qui prétendent à une éternité (de bonheur ou de souffrance) après la mort pensent vraiment à une durée supérieure à ce nombre d'années ? Est-ce que ça a un sens de se demander ce que vaut le N-ième chiffre de π ? et de la constante de structure fine pour N un de ces nombres gigantesques ?

En fait, s'agissant de ce qui se passera dans N années, si je ne m'abuse, la réponse de la physique telle que nous la comprenons est essentiellement : tout. Car les fluctuations du vide sont suffisantes pour faire — de façon extrêmement improbable, mais essentiellement certaine si on attend les durées démesurées dont nous parlons ici — littéralement apparaître du vide n'importe quoi. (Y compris un nouvel Univers. Voir aussi cette entrée et la suivante pour quelques réflexions dans cet ordre d'idées.)

La contemplation de ces monstres conceptuels a quelque chose de terrifiant : à quoi servent-ils ? pourquoi sont-ils là ? sont-ils vraiment là ? (même parmi les mathématiciens, il y a des gens qui en doutent, notamment, si je comprends bien sa position, un certain médaillé Fields ; voir une entrée ultérieure pour mon avis à ce sujet).