• Notations de Knuth et Conway pour les très grands nombres entiers

    La mathesis fait mentir la sagesse paulinienne : il n'est plus vrai que la lettre tue et l'esprit vivifie, et l'on pourrait même dire que la lettre (ou plutôt la notation, le diagramme) EST l'esprit lui même se frayant une voie pour "souffler où il veut"...mais aussi où il peut.

    Certes une notation mathématique nouvelle n'est pas un nouveau concept mathématique : on pourrait toujours écrire le nouveau (l'esprit qui souffle où il veut) dans les anciennes notations....sauf quand on ne peut pas !

    C'est à la suite de la lecture inopinée du passage d'un livre prodigieux, "Ramsey theory", que je me suis intéressé aux fonctions ackermaniennes et à leur hiérarchie, parce qu'elles sont accompagnées d'une nouvelle notation pour les très grands nombres, et sont donc susceptibles d'apporter des éclaircissements à propos de ce que j'appelle le MONSTRE, à savoir un nombre qui "formalise" la preuve d'Anselme de l'existence de Dieu comme maximum, "ce dont un plus grand ne peut être pensé".

    Ce livre extraordinaire sur la théorie de Ramsey est accessible sur Google :

    http://books.google.fr/books?id=55oXT60dC54C&pg=PA60&lpg=PA60&dq=Ramsey+theory+ackerman+hierarchy&source=bl&ots=LnGd0HMLvo&sig=epSj0G1aTVhl_vq_kGjqc-9PzXI&hl=fr&ei=rioES_OzONONjAf0p_24AQ&sa=X&oi=book_result&ct=result&resnum=1&ved=0CAsQ6AEwAA#v=onepage&q=&f=false

    on y parle de la hiérarchie d'Ackerman en paragraphe 2.7 page 60 : "Eeeeenormous upper bounds".

    C'est un livre captivant mais difficile, je l'ai en ma possession depuis environ 15 ans et je ne l'ai toujours pas exploré en entier, il est vrai que les traités de mathématiques, surtout quand ils sont ardus comme celui là, ne se lisent pas à la manière des romans.

    Mais on peut trouver un court article , écrit par deux des auteurs du livre, Ronald Graham et Joel Spencer, qui livrent en peu de mots l'esprit philosophique de la théorie de Ramsey, qui est une confirmation des analyses de Bergson sur le "désordre et les deux ordres" : le désordre absolu est impossible, tout ensemble assez grand de nombres ou de points possède des régularités et des symétries étonnantes , voir :

    http://www.math.ucsd.edu/~sbutler/ron/90_06_ramsey_theory.pdf

    La fonction d'Ackermann (datant de 1928 il me semble) est obtenue par un procédé de diagonalisation d'une hiérarchie de fonctions généralisant les opérations élémentaires de multiplication et exponentiation, qui ne sont que les étages les plus bas d'une tour prodigieuse (babélienne?) : cette hiérarchie de fonctions, croissant de plus en plus vite, commence avec f1(x) = 2x , suivie de l'exponentielle f2(x) = 2x , puis par la fonction f3  appelée  TOWER (tour) qui consiste en une tour de 2 puissance 2 puissance 2.... x fois.

    On passe ensuite à la fonction f4  appelée par nos auteurs WOW parce qu'on ne peut que pousser un cri de surprise : WOW devant l'immensité des nombres qu'elle met déjà en jeu (rien qu'au bout de 4 itérations). La suite infinie est définie par une double induction, voir la page 60 du livre, et la fonction d'Ackermann croît plus vite que TOUTE fonction de la suite, aussi bien que de toute fonction primitivement récursive, car elle est obtenue par diagonalisation , c'est à dire que l'on ne prend plus un indice fixe fi (x), mais on fait varier l'indice avec x :

    Ackermann (x) = fx(x)

     Voir là dessus un lien plus complet car plus restreint au sujet des fonctions ackermaniennes :

    http://en.wikipedia.org/wiki/Ackermann_function

    il y a aussi des fonctions "Ackermann inverse", qui croissent avec une lenteur prodigieuse, voir liens à la fin de celui ci dessus.

    Mais ce lien cite, et c'est là que je veux surtout en venir, car je pense toujours au MONSTRE, jour et nuit, des notations aptes à faciliter la compréhension des nombres extrêmement grands.

    Ceux ci forment, avec les grands cardinaux (qui sont autre chose, là nous nous restreignons aux entiers, bornés donc par l'infini dénombrable qui est le cardinal infini le plus bas, Aleph zéro de Cantor) un sujet de réflexions passionnées pour pas mal de mordus, dont votre serviteur... voir le site de Munafo, qui avoue carrément y avoir consacré une grande partie de sa vie, comme le capitaine Achab à la poursuite de la baleine blanche dans Moby dick de Melville :

    http://www.mrob.com/pub/math/largenum.html

     Les notations (inventées au 20 ème siècle) pour les très grands nombres sont des généralisations, sur le mode de la hiérarchie des fonctions d'Ackermann, des opérations élémentaires, qui sont :

    l'opération "successeur" (qui correspond à un des axiomes de Peano pour les nombres entiers) : à un nombre entier a on associe son successeur a + 1

    l'addition : on obtient à partir de l'entier a le nouvel entier a + b en itérant b fois l'opération "successeur" : a + 1 + 1 + 1...+ 1 (on ajoute 1 b fois)

    la multiplication : pour obtenir le produit a x b à partir de l'entier a on itère b fois l'opération précédente d'addition, c'est à dire qu'on ajoute b fois l'entier a à lui même:

    a x b = a + a +... + a (b fois)

    l'exponentiation : là encore on itère b fois l'opération précédente (multiplication) pour obtenir a à la puissance b :

    ab =  a x a x a x .... x a  (b fois)

    à partir de là nous quittons le domaine des opérations courantes pour entrer dans celui des "tours d'exposants", qui peuvent encore à la rigueur s'exposer dans le langage de l'exponentiation, mais où de nouvelles notations rendent de grands services de simplification et de clarification. Le procédé de récurrence sera toujours le même : on passe d'une opération à la suivante, dans une hiérarchie ackermanienne qui n'a pas de fin, en itérant celle ci b fois.

    Notation de Knuth avec des flèches verticales orientées vers le haut (up-arrows)

    ainsi l'opération suivant l'exponentiation correspond elle à la fonction d'Ackermann TOWER = f3  . Elle peut s'écrire d'abord dans la notation en flèches verticales inventée par Knuth: on notera d'abord, dans cette notation nouvelle qui est comme un nouveau langage, l'exponentiation avec une flèche verticale vers le haut :

    ab = a \uparrow b

    l'opération suivant l'exponentiation , consistant à itérer celle ci, sera notée naturellement avec deux flèches vers le haut :

     \uparrow\uparrow b  = a \uparrow a ... \uparrow...\uparrow a (b fois)

    Cela consiste en une "tour" de a puissance a puissance a  etc... , ceci b fois.

     

    Attnetion, l'opération d'exponentiation n'est pas associative, ni commutative d'ailleurs : elle est "associative à droite" (right-associative), c'est à dire qu'il faut partir de la droite et remonter vers la gauche.

    exemple :  3 puissance 3 puissance 2 = 3^3^2 est  égal à : 3 ^(3 ^2 ) = 3 ^9 (3 puissance 9) et non à : (3^3) ^2 = 27 ^2 ( 27 puissance 2) .

    On procèdera ainsi de suite avec trois flèches, quatre, n , etc... :

    a \uparrow \uparrow \uparrow b  = a \uparrow\uparrow ...  \uparrow\uparrow a (b fois)

    Comme cela devient trop compliqué à partir de 4 ou 5 on notera :    \uparrow^n  l'opération consistant en n flèches orientées vers le haut.

    a \uparrow^n b = a ... \uparrow...\uparrow a    (avec n flèches)

    Voir ce lien pour des explications complètes :   http://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation

    (on lira notamment le paragraphe "Writing out up-arrow notation in terms of powers" pour avoir une idée de l'énormité des nombres mis en jeu à partir de trois ou quatre flèches...et que l'on pense que l'on peut augmenter le nombre des flèches à l'infini !).

    Notation de Conway avec des flèches horizontales en chaîne :

    C'est une notation équivalente, plus pratique dans certains cas, moins dans d'autres ; mais en tout cas elle est plus facile avec les outils (assez restreitns) que Blogg met à ma disposition, ce sera donc celle que j'utiliserai surtout à l'avenir ... elle est expliquée sur ce lien :

    http://en.wikipedia.org/wiki/Conway_chained_arrow_notation

    Ici l'exponentiation est aussi notée par une flèche (comme chez Knuth) mais horizontale (comme un morphisme dans une catégorie, ou une application entre ensembles, mais attention, ici les flèches ne se composent pas entre elles !):

     ab = a \uparrow b  (Knuth)  = a → b (Conway)

    Comment traduit on les 2 flèches, 3 flèches, n flèches de Knuth ? pas avec deux, trois, ou n flèches horizontales, car cela serait trop difficile (surtout sur Internet et sur Blogg notamment !).

    non, le coup de génie de Conway est d'avoir permis à une deuxième flèche de faire son apparition . L'opération "Tower", avec deux flèches, devient dans la notation de Conway :

    \uparrow\uparrow b =  a → b → 2

    et ainsi de suite, pour trois, quatre, n flèches de Knuth : deux flèches de Conway suffisent :

     a \uparrow^n b = a ... \uparrow...\uparrow a    (avec n flèches) =  a → b → n

    Incroyablement simple et intelligent, n'est ce pas ?

    C'est dans ce genre de situations que l'invention d'une nouvelle notation, en mathématiques, à condition bien sûr qu'elle soit féconde, est beaucoup plus que de simple nature "formelle" : disons que le "contenu" descend avec, s'incarne dans la forme. L'exemple paradigmatique de ceci est la théorie des catégories, où le simple ajout d'une flèche (d'un morphisme) , puis d'un diagramme plus ou moins complexe de flèches, permet de trouver, de créer ( ?) des "essences mathématiques" tout à fait inédites.

     Car les flèches de Conway peuvent s'inclure dans des schémas bien plus complexes, qu'il est possible de "calculer" à partir des quatre règles données dans le lien ci dessus, au début.

    C'est ainsi (voir le lien) que l'on peut montrer assez vite que :

    a→ b → 2 → 2 = a → b → ab

    Hyperoperations :

    Les deux notations précédentes peuvent se fondre dans le cadre conceptuel des hyperopérations, expliquées dans le lien suivant :

    http://en.wikipedia.org/wiki/Hyper_operator

     Les opérations appelées précédemment , successeur, addition, multiplication, exponentiation sont respectivement : Hyper0, hyper1, hyper2 et hyper3. En fait Hypern  correspond à (n-2) flèches verticales dans la notation de Knuth, on pourra donc noter :

     a \uparrow^n b = a ... \uparrow...\uparrow a    (avec n flèches) =  a → b → n  = Hn+2 (a,b)

    H4  s'appelle tetration : http://en.wikipedia.org/wiki/Tetration

    mais les hyperoperations peuvent prendre d'autres formes.

    Encore quelques sites à lire pour ceux que le sujet passionne (ce qui est mon cas) :

    http://en.wikipedia.org/wiki/Pentation

    http://en.wikipedia.org/wiki/Steinhaus-Moser_notation

    http://www-users.cs.york.ac.uk/~susan/cyc/b/big.htm

    Dans un article à venir on utilisera ce genre de notations pour simplifier les expressions des séries menant au MONSTRE, c'est à dire au nombre entier "infini" que nous avons défini d'après sa décomposition "développée" en facteurs premiers comme "le plus grand" : un nombre infini d'échelons d'exposants et à chaque échelon tous les nombres premiers, en nombre infini.

     


    Tags Tags : , , , , , , , ,
  • Commentaires

    Aucun commentaire pour le moment

    Suivre le flux RSS des commentaires


    Ajouter un commentaire

    Nom / Pseudo :

    E-mail (facultatif) :

    Site Web (facultatif) :

    Commentaire :