Notation des flèches chaînées de Conway

La notation des flèches chaînées de Conway est une notation créée par le mathématicien John Horton Conway, permettant d'exprimer de très grands nombres. Elle consiste en une suite finie d'entiers positifs séparés par des flèches, comme Comme beaucoup d'autres expressions combinatoires, sa définition est récursive. Au bout du compte, elle revient à élever le nombre le plus à gauche à une puissance entière et généralement énorme. Du point de vue de la notation, une chaîne de Conway (ou chaîne) est définie récursivement de la manière suivante : tout entier positif constitue (à lui seul) une chaîne de longueur 1 ; une chaîne de longueur est constituée par une chaîne de longueur (la « queue »), suivie d'une flèche , suivie d'un entier positif (la « tête » de la chaîne). Une chaîne Y qui n'est pas incluse dans une chaîne plus longue, de la forme , , ou , est dite chaîne complète. Dans la définition suivante, et sont des nombres entiers positifs et est une chaîne dont la valeur est supposée connue (en cela, la définition est récursive). On pose : (exponentiation) (et donc ) avec p+1 copies de la chaîne X, p copies de q, et p paires de parenthèses. La troisième règle (le cas général) est bien entendu le cœur de la définition. Avec ce mécanisme de réécriture, une chaîne de longueur 3 ou plus se terminant par un entier supérieur ou égal à 2 peut se réécrire sous la forme d'une chaîne de même longueur, avec un pénultième élément immensément plus grand, mais un dernier élément décrémenté d'une unité. En appliquant cette règle de manière itérative, la décrémentation du dernier élément le réduit finalement à 1, ce qui permet de réduire la longueur de la chaîne d'une unité (règle 2). Après (pour reprendre l'expression de Knuth), la chaîne finit par être réduite à deux éléments, ce qui permet de conclure (règle 1). Sous forme de programme récursif, la réduction s'écrit (si la chaîne est de longueur au moins deux): function Conway(X: chaîne; p, q: Naturel): naturel 'begin' if (X=vide) then R:=p^q elseif (q=1) then R:=Conway(Queue(X), Tête(X), p) 'else begin' R:=Conway(X,1,1) for ctr:=1 to p-1 do R:=Conway(X,R,q-1) end return R end N.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés (6)

Tétration

La tétration (ou encore nappe exponentielle, hyperpuissance, tour de puissances, super-exponentiation ou hyper4) est une « exponentiation itérée ». C'est le premier hyperopérateur après l'exponentiation. Le mot-valise tétration a été forgé par Reuben Goodstein sur la base du préfixe tétra- (quatre) et itération. La tétration est utilisée pour l'écriture des grands nombres. Elle suit l'addition, la multiplication et l'exponentiation comme indiqué ci-après : addition multiplication exponentiation tétration avec chaque fois b apparitions de la lettre a.

Pentation

vignette|Les trois premières valeurs de l'expression x[5]2. La valeur de 3[5]2 est d'environ 7,626 × 1012 ; les valeurs pour les x plus élevés, comme 4[5]2, qui est d'environ 2,361 × 108,072 × 10153, sont beaucoup trop grandes pour apparaître sur le graphique. La pentation est la répétition de l'opération de tétration, comme la tétration est la répétition de l'opération d'exponentiation. La pentation est une hyperopération. Comme la tétration, la pentation a peu d'applications dans la vie courante.