Auteur: Serge Boisse
Date: Le 27/03/2023 à 12:03
Type: web/MOC
Tags: 
pub: oui
commentaires: ouiCopier

Le plus grand entier : les grands nombres sont rares

Il y a quelques années, un journal scientifique (scientific american, je crois) a publié le concours suivant auprès de ses lecteurs, doté d'un prix pouvant aller jusqu'à un milliard de dollars (si !) :

Le gagnant est celui qui écrirait le plus grand nombre entier n sur une carte postale à renvoyer au journal. Toutes les notations mathématiques usuelles étaient autorisées, et même les autres à condition de les décrire, c'est à dire de décrire le moyen de calculer le nombre résultat.

                 Le prix était un milliard de dollars, divisé par le nombre gagnant.

Qu'auriez vous dû répondre pour gagner ? Quel est le plus grand nombre qui peut s'écrire ou se décrire sur une carte postale ?

Des idées assez courantes

Il est évident que remplir la carte de "9" n'était pas très efficace : avec une centaine de tels 9, le nombre obtenu est plus petit que 10100.
Une autre idée assez commune est d'écrire 9!!!!!!!!!.... avec une centaine de points d'exclamations derrière. On se souvient en effet que le nombre n! , qui se lit "factorielle de n" est le produit des nombres inférieurs ou égaux à n : ainsi 9! = 9x8x7x6x5x5x3x2x1 = 362880.
9!! est la factorielle de 362880, ce qui est déjà beaucoup plus grand. Comment le calculer au fait ?  Le nombre 70! dépasse déjà ${10}^{99}$, ce qui est la plus grande valeur affichable sur une calculette scientifique. En fait, si on se souvient (!) de la formule de Stirling :

$n!\sim \sqrt{2\pi n}(n/e{)}^n$

On a $\log (n!)\sim \log (n)/2+n(\log (n)-1)\sim n\log (n)$ pour de grands n : donc $log(9!!)\sim 9!\times log(9!)=4\times {10}^6$, donc 9!! a environ 4 millions de chiffres : déjà un beau nombre.

Quand à 9!!!!...! avec 100 "!", c'est un nombre absolument gigantesque. Si ce nombre gagne le concours, il ne gagne... absolument rien, sinon la gloire. Mais on pouvait faire bien mieux : par exemple on écrirait sur la carte postale :

soit f(n) la fonction définie par f(n) = 9!!!...!  
   avec n signes "!"_  
je propose le nombre f(f(f(9)))
Copier

ou tout autre nombre de la même veine.

En fait dès que l'on a défini une fonction f(n) qui croît "très vite", on peut définir une autre fonction g qui est l'itérée de f, n fois : g(n) = f(f(...(f(n))..) avec n fois la lettre f.

Plus rigoureusement, on peut définir g par récurrence :

Soit la fonction g(n) définie par :
g(0) = 9  
Pour tout n > 0, g(n) = f(g(n-1)).
Copier

Et rien n'empêche de définir une nouvelle fonction, h, qui serait l'itérée de g, et ainsi de suite.

Tours de puissances

On arrive ainsi tout naturellement a l'idée de tours de puissances : On peut noter :

• 2^n = 2n,
• 2^^n = un empilement de 2^n de taille n, c'est à dire : 2^^0 = n, et pour tout n > 0, 2^^n = 22^^(n-1)
• 2^^^n défini par : 2^^^0 = n et pour tout n > 0, 2^^^n = 22^^^(n-1)
• 2^^^^n = ... etc.

Et proposer comme solution le nombre 2^^^^·....^9 avec une centaine de "^".

Ça vous étonnera peut être, mais on pouvait faire encore mieux : en fait le processus "tours de puissance", à la limite, donne ce que l'on nomme la fonction d'ackerman.

La fonction d'ackerman

Elle est défini comme suit :
ackerman(n) = a(n,n), où a() est la fonction de deux entiers définie comme suit :

-   Pour tout n >= 0, a(0,n) = n+1
-   pour tout n > 0, a(n,0) = a(n-1, 1).
-   pour tout n > 0 et tout m > 0,  a(n,m) = a(n-1, a(n, m-1))
Copier

Amusons nous a calculer ackerman(2) = a(2,2) :

a(2,2) = a(1, a(2, 1)) : il faut donc calculer a(2,1)

   a(2,1) = a(1, a(2, 0)) : il faut donc calculer a(2, 0)

      a(2,0) = a(1, 1) : il faut donc calculer a(1,1)

          a(1,1) = a(0, a(1, 0)) : il faut donc calculer a(1,0)

              a(1,0) = a(0, 1) = 2

          a(1,1) = a(0,2) = 3

      a(2,0) = 3

   a(2,1) =  a(1,3) = a(0, a(1, 2))  : il faut donc calculer a(1,2)

      a(1,2) = a(0,a(1, 1)) = a(0,3) = 4     {a(1,1) déjà calculé = 3}

   a(2,1) = a(0, 4) = 5

a(2,2) = a(1,5) : il faut donc calculer a(1,5)

   a(1,5) = a(0, a(1, 4)) : il faut donc calculer a(1,4)

      a(1,4) = a(0, a(1,3))  = a(0,5) = 6      {a(1,3) déjà calculé = 5}

   a(1,5) = a(0,6) = 7

a(2,2) = 7

De même on trouverait ackerman(3) = 61. Quand à ackerman(4) ... n'essayez pas de le calculer a la main.. et même à l'ordinateur !

Cette "petite" fonction, la fonction d'ackermann, croît plus vite que n'importe quelle tour de puissance. Ceci signifie que au delà d'un certain rang n, toutes les valeurs de la fonction sont plus grandes que celles d'une tour de puissance quelconque. En effet ackerman(n) ~ 2^^ ... ^n avec n symboles "n".

On pouvait donc répondre au concours avec
ackerman(ackerman(....ackerman(9)....))  avec une centaine de fois le mot "ackerman" (je vous rappelle que ça doit tenir sur une carte postale). Ce nombre gigantesque est absolument inimaginable. Le nombre de chiffres du nombres de chiffres.... etc. (en écrivant un bon million de fois "le nombre de chiffres du") du nombre de chiffres de ce nombre, ne tiendrait pas dans une feuille de papier de la taille de l'univers !

Voici une variante un peu plus intuitive de la fonction d'ackermann :

• A(a,n,1) = a+n
• pour j différent de 1, A(a,1,j) = a
• pour n et j  différents de 1, A(a,n,j) =  A(a, A(a, n-1, j), j-1)

Il n'est pas difficile de voir que
A(a,n,1) = a+n
A(a,n,2) = a * n
A(a,n,3) = a ^ n
A(a,n,4) = a^^n = a^a^a^a... (n fois)

Qui va gagner ?

Nous avons donc deux problèmes :

• face a de très grands nombres définis par une fonction de ce style, comment trouver lequel est le plus grand pour désigner le vainqueur du concours ?
• peux-t-on encore faire plus grand ?

En fait la réponse à la première question est "non". face à des nombres définis par des fonctions, il n'existe pas d'algorithme général qui puisse déterminer quelle est la fonction qui croît le plus rapidement.

Par exemple je vous propose une autre fonction : f(n) = tan(pi/2 - 2-n)

On sait que tan(x) tend vers l'infini lorsque x se rapproche de pi/2. Alors, quelle est la fonction la plus "rapide" ? ackerman(n) ou f(n) ? bien malin qui le dirait...

Pourtant, ici, c'est facile :  tan(pi/2 - 2-n) ~ 1/cos(pi/2 - 2-n) = 1/sin(2-n)  ~ 2-n.  ya pas photo ! Mais dans le cas général c'est très difficile.

La fonction siglma ($\sigma$) de Rado

Quand à la seconde question, "pouvait-t-on faire encore mieux" ? La réponse est "oui, mais en utilisant des fonctions non calculables". Qu'est ce que cela veut dire ?

Pour le savoir, réfléchissons un  peu : ce que nous avons essayé de faire jusqu'à présent, c'est de trouver le plus grand entier que l'on peut décrire sur une carte postale, c'est à dire, disons, en moins de 1000 signes. En fait, comme nos entiers sont définis par des fonctions, nous avons essayé de trouver la fonction descriptible en moins de 1000 signes qui croît le plus rapidement. Il existe une formalisation de cela : c'est la notion de complexité algorithmique d'un nombre.

La complexité algorithmique d'un nombre, c'est la taille du plus petit programme qui permet de le calculer. Peu importe quel langage mathématique ou informatique on utilise : pour de très grands nombres, la complexité de ces nombres sera a peu près la même que l'on utilise l'un ou l'autre langage. Dans la pratique on utilise souvent un modèle abstrait de machine à calculer que l'on appelle la machine de turing. La taille d'une machine de turing est donnée par son nombre d'états possibles. Peu importe ce que cela veut dire,

La complexité d'un nombre, c'est la taille du plus petit programme écrit pour une machine de turing qui calcule (imprime) ce nombre.

Et voici la définition de la fonction de Rado, inventée par le mathématicien Tibor Rado, et souvent notée sigma(n) : $\sigma (n)$

C'est à peu près le plus grand nombre que l'on peut décrire par un programme d'ordinateur de taille n bits. sigma(n) croit plus vite que n'importe quelle fonction de n que l'on peut décrire en moins de n signes. Le nombre sigma(1000) est donc le vainqueur absolu de notre concours, puisque pour définir un nombre plus grand il faudrait plus de 1000 signes par définition.

Le seul hic, c'est que sigma(n) n'est pas calculable....

preuve : supposons que l'on dispose d'un programme P de longueur p qui calcule sigma(n) pour tout n :

Par définition de sigma, il faut un programme d'au moins n signes pour calculer sigma(n). Mais, avec notre programme magique p, il suffit de ${\log }_{10}(n)+10+p$ bits :
"print P(999)" fait en effet 10+3 signes (les trois chiffres de 999, soit $lo{g}_{10}(999)\sim 3$)
d'où contradiction pour des n suffisamment grands, peu importe le langage.

En fait la fonction sigma n'est pas calculable, parce qu'elle croit trop rapidement. Pour n > 50 (a peu près) on a déjà sigma(n) bien plus grand que ackermann(n)... Sigma de n est la fonction qui croît le plus vite que l'on puisse imaginer. Le fait qu'elle ne soit pas calculable montre que c'est la borne supérieure des fonctions croissantes calculables.

Remarque : Bien que sigma(n) soit non calculable, on peut essayer de la calculer, ou tout d'un moins d'en calculer des minorants, pour les très petits entiers. C'est le problème du castor affairé, un "sport" assez amusant.

Les très grands entiers.... sont rares

Il faut bien avoir conscience de l'énorme différence qui existe entre ackermann(8) et ackermann(9) : ces deux nombres sont tous les deux gigantesques, mais le second est presque infiniment plus grand que le premier ! Que dire alors de l'écart entre ackermann(ackermann(8)) et ackermann(ackermann(9) ) !! Ces deux nombres sont inimaginablement grands, pourtant entre eux il existe un écart insondable. Il n'est pas possible de "remplir" cet écart avec des nombres fabriqués par des programmes raisonnablement courts (disons, plus petits que le nombre de protons de l'univers, 10^88, qui est comparativement un nombre ridiculement minuscule)...

On peut inventer autant de définitions que l'on voudra, pour des très grands nombres de l'ordre de ackermann(ackermann(9) ), on ne parviendra pas à "remplir" l'énorme "trou" qui existe entre deux quelconques de ces très grands nombres : contrairement à l'idée commune, les très grands nombres... sont très rares. Certes, a partir d'un très grands nombre n, on peut construire n+1, n+2, 2n... mais ce n'est pas ainsi (du moins si l'on ne veut pas y consacrer des millions d'années) que l'on remplira les "trous" : autour d'un très grands nombre quelconque n, il y a quelques nombres dont la complexité est voisine, mais si l'on veut par exemple lister tous les nombres entre ackermann(8) et ackermann(9) , on va devoir monter jusqu'à des complexités affolantes, du même ordre de grandeur en fait que ackerman(9) !

La raison en est que la plupart des très grands nombres sont aléatoires, c'est à dire que leur complexité est du même ordre qu'eux même (ou de leur logarithme, pour être plus précis) : pour ces nombres, il n'y a pas de programme vraiment plus court que "écrire n" en extension... La grande majorité des très grands nombres échappe littéralement à notre entendement : ces nombres aléatoires n'ont absolument aucune chance d'apparaître un jour sur l'écran ou dans la mémoire d'un ordinateur situé dans notre univers !

Je prétends donc que les nombres entiers ne sont pas en nombre infinis : leur nombre est borné par le nombre des programmes que nous saurons un jour écrire ou imaginer pour les fabriquer ou les concevoir.

On peut essayer de "classer" les entiers par ordre de complexité croissante. Le nombre d'entiers de complexité c croit avec c en général, mais reste assez petit (pour un programme de n bits, il y a seulement  2^n programmes en binaire, et la grande majorité de ces programmes seront incorrects ou boucleront ou ne s'arrêteront jamais, quelque soit le langage utilisé). Inversement, on peut essayer de représenter la complexité des nombres, classés selon l'ordre naturel. On obtient a peu près ça :

Un univers construit avec la fonction sigma : cliquer ici

> La suite : Les nombres premiers
> index maths