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.