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

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

La notation des flèches chaînées de Conway est un moyen d'exprimer de très grands nombres créée par le mathématicien John Horton Conway. Elle consiste en une suite finie d'entiers positifs séparés par des flèches, comme par exemple 2\rightarrow 31\rightarrow 14\rightarrow 5\rightarrow 623.

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.

Sommaire

Définition

Définition des chaînes

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 n + 1 est constituée par: une chaîne de longueur n (la "queue"), suivie d'une flèche \rightarrow, 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 X\rightarrow Y, Y\rightarrow Z, ou X\rightarrow Y\rightarrow Z, est dite chaîne complète.

Valeur d'une chaîne

Dans la définition suivante, p\,\! et q\,\! sont des nombres entiers positifs et X\,\! est une chaîne dont la valeur est supposée connue (en cela, la définition est récursive). On pose :

  1. p\rightarrow q=p^q\,\! (exponentiation)
  2. X\rightarrow 1=X\,\! (et donc p\rightarrow 1=p\,\!)
  3. X\rightarrow p\rightarrow (q+1) = X\rightarrow \left( X\rightarrow \left( \ldots X\rightarrow \left( X \right) \rightarrow q \ldots \right) \rightarrow q \right) \rightarrow q,

avec p copies de la chaîne X, p-1 copies de q, et p-1 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 applicant 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 "de très nombreuses étapes intermédiaires" (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

NB: N'essayez surtout pas de programmer un tel programme, son temps d'exécution sera généralement inimaginablement supérieur à l'âge de l'univers...

Exemples simples

En explicitant un peu :

  • Une chaîne de longueur 1 est juste un nombre : p\,\!
  • Une chaîne de longueur 2 est un nombre élevé à une puissance entière: p^q\,\!
  • Une chaîne de longueur 3 correspond à la notation de Knuth et à l'hyper opérateur :
\begin{matrix} p \to q \to r = \mbox{hyper}(p,r+2,q) = p \underbrace{ \uparrow \dots \uparrow } q = p\uparrow^r q\\ \qquad\ \qquad\ \qquad\ \qquad\ \qquad\ \qquad\quad\ r \mbox{ fleches} \end{matrix}.
  • Une chaîne de longueur 4 est généralement trop grande pour être facilement exprimée avec un opérateur de Knuth, c'est pourquoi cette notation devient pratique.

Propriétés

Cette notation n'est pas associative. En effet :

  • 2\rightarrow 3\rightarrow 2 = 2\uparrow \uparrow 3 = 2^{2^2} = 16
  • 2\rightarrow \left(3\rightarrow 2\right) = 2^{3^2} = 512
  • \left(2\rightarrow 3\right)\rightarrow 2 = \left(2^3\right)^2 = 64

La chaîne X\rightarrow p\rightarrow q\,\! peut toujours être exprimée sous la forme X\rightarrow r\,\!, où r\,\! est un nombre entier considérablement plus grand que p\,\! et q\,\!.

Par conséquent :

  • Une chaîne commençant par a\,\! est une puissance de a\,\!
  • Une chaîne commençant par 1 est égale à 1, puisqu'elle s'écrira finalement 1n=1. En fait, toute chaîne contenant un 1 peut être tronquée juste avant ce 1: X\rightarrow 1\rightarrow Y = X pour toutes chaînes X et Y. Cela se démontre par récurrence sur la taille et la dernière valeur de la chaine Y. On peut au final toujours la réduire sous la forme X\rightarrow 1\rightarrow n qui se réécrit en X.
  • Une chaîne commençant par 2\rightarrow 2\,\! est de la forme 2\rightarrow 2\rightarrow p\,\! et donc égale à 4 (voir ci-dessous).

Les cas les plus simples avec quatre nombres sont :

  • a\rightarrow b\rightarrow 2\rightarrow 2 = a\rightarrow b\rightarrow a^b\,\!
  • a\rightarrow b\rightarrow 3\rightarrow 2 = a\rightarrow b\rightarrow \left(a\rightarrow b\rightarrow a^b \right)

Si pour une chaîne X\,\! on définit la fonction f(n)=X\rightarrow n\,\!, alors X\rightarrow p\rightarrow 2 = f^p(1)\,\! (voir Composition de fonctions).

Exemples

Il est difficile de donner des exemples pertinents, car ils requièrent 4 éléments et correspondent à des nombres beaucoup trop grands pour pouvoir être explicités. Cependant, dans les exemples suivants, les numéros entre parenthèses à la fin de chaque ligne indiquent quelle partie de la définition de la notation a été utilisée pour passer d'une ligne à l'autre.

  • 4\rightarrow 3\rightarrow 2\,\!
= 4\rightarrow (4\rightarrow (4)\rightarrow 1)\rightarrow 1\,\! (3) (désormais, les paires de parenthèses inutiles, comme ici, ne seront plus systématiquement indiquées)
= 4\rightarrow (4\rightarrow 4)\,\! (2)
= 4\rightarrow \left(4^4\right)\,\! (1)
= 4^{256}\,\! (1)
= 1,34\times 10^{154}, approximativement

Avec la notation de Knuth : 4\rightarrow 3\rightarrow 2 = 4\uparrow \uparrow 3=4^{4^4}\,\!

  • 2\rightarrow 2\rightarrow 4\,\!
= 2\rightarrow 2\rightarrow 3\,\! (3)
= 2\rightarrow 2\rightarrow 2\,\! (3)
= 2\rightarrow 2\rightarrow 1\,\! (3)
= 2\rightarrow 2\,\! (2)
= 2^2\,\! (1)
= 4\,\!

En fait, toute chaîne commençant par deux 2 est égale à 4.

  • 2\rightarrow 4\rightarrow 3\,\!
= 2\rightarrow (2\rightarrow (2\rightarrow 2\rightarrow 2)\rightarrow 2)\rightarrow 2\,\! (3)
= 2\rightarrow (2\rightarrow 4\rightarrow 2)\rightarrow 2\,\! (d'après l'exemple précédent)
= 2\rightarrow(2\rightarrow (2\rightarrow (2\rightarrow 2\rightarrow 1)\rightarrow 1)\rightarrow 1)\rightarrow 2\,\! (3)
= 2\rightarrow (2\rightarrow (2\rightarrow (2\rightarrow 2)))\rightarrow 2\,\! (2)
= 2\rightarrow (2\rightarrow (2\rightarrow (4)))\rightarrow 2\,\! (1)
= 2\rightarrow (2\rightarrow 16)\rightarrow 2\,\! (1)
= 2\rightarrow 65536\rightarrow 2\,\! (1)
= 2\rightarrow (2\rightarrow (2\rightarrow (\ldots 2\rightarrow (2\rightarrow (2)\rightarrow 1)\rightarrow 1...)\rightarrow 1)\rightarrow 1)\rightarrow 1\,\! (3) avec 65 535 paires de parenthèses
= 2\rightarrow (2\rightarrow (2\rightarrow (\ldots 2\rightarrow (2\rightarrow 2)\ldots )))\,\! (2)
= 2\rightarrow (2\rightarrow (2\rightarrow (\ldots 2\rightarrow 4\ldots )))\,\! (1)
= 2\rightarrow (2\rightarrow (2\rightarrow (\ldots 16\ldots )))\,\! (1)
= 2\rightarrow \left(2^N\right)\,\! (1)
= 2^{2^N}\,\!

où N\,\! est un nombre extrêmement grand.

Il est possible d'écrire l'expression précédente à l'aide de la notation de Knuth :

2\rightarrow 4\rightarrow 3 = 2\uparrow \uparrow \uparrow4 = 2\uparrow \uparrow 2\uparrow \uparrow 2\uparrow \uparrow 2=2\uparrow \uparrow 2\uparrow \uparrow 4=2\uparrow \uparrow 2\uparrow 2\uparrow 2\uparrow 2=2\uparrow \uparrow 65536\,\!

  • 2\rightarrow 3\rightarrow 2\rightarrow 2\,\!
= 2\rightarrow 3\rightarrow (2\rightarrow 3)\rightarrow 1\,\! (3)
= 2\rightarrow 3\rightarrow 8\,\! (1 et 2)
= 2\rightarrow (2\rightarrow 2\rightarrow 7)\rightarrow 7\,\! (3)
= 2\rightarrow 4\rightarrow 7\,\! (voir ci-dessus)
= 2\rightarrow (2\rightarrow (2\rightarrow 2\rightarrow 6)\rightarrow 6)\rightarrow 6\,\! (3)
= 2\rightarrow (2\rightarrow 4\rightarrow 6)\rightarrow 6\,\! (voir ci-dessus)
= 2\rightarrow (2\rightarrow (2\rightarrow 4\rightarrow 5)\rightarrow 5)\rightarrow 6\,\! (id.)
= 2\rightarrow (2\rightarrow (2\rightarrow (2\rightarrow 4\rightarrow 4)\rightarrow 4)\rightarrow 5)\rightarrow 6\,\! (id.)
= 2\rightarrow (2\rightarrow (2\rightarrow (2\rightarrow (2\rightarrow 4\rightarrow 3)\rightarrow 3)\rightarrow 4)\rightarrow 5)\rightarrow 6\,\! (id.)
= 2\rightarrow (2\rightarrow (2\rightarrow (2\rightarrow 2^{2^N}\rightarrow 3)\rightarrow 4)\rightarrow 5)\rightarrow 6\,\! (d'après l'exemple précédent)

Ici, il devient impossible d'expliciter le nombre plus avant.

À l'aide de la notation de Knuth : 2\rightarrow 3\rightarrow 2\rightarrow 2= 2\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow 2\uparrow \uparrow \uparrow \uparrow \uparrow 2\uparrow \uparrow \uparrow \uparrow 2\uparrow \uparrow \uparrow 2\uparrow \uparrow 65536\,\!.

  • 3\rightarrow 2\rightarrow 2\rightarrow 2\,\!
= 3\rightarrow 2\rightarrow (3\rightarrow 2)\rightarrow 1\,\! (3)
= 3\rightarrow 2\rightarrow 9\,\! (1 et 2)
= 3\rightarrow 3\rightarrow 8\,\! (3)

Ce qui correspond à un nombre proprement gigantesque.

À l'aide de la notation de Knuth : 3\rightarrow 2\rightarrow 2\rightarrow 2 = 3\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow 3\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow 3\uparrow \uparrow \uparrow \uparrow \uparrow 3\uparrow \uparrow \uparrow \uparrow 3\uparrow \uparrow \uparrow 3\uparrow \uparrow 7,6\times 10^{12}\,\!

Fonction d'Ackermann

La fonction d'Ackermann peut être exprimée à l'aide de la notation de Conway :

A(m, n) = (2 \rightarrow n+3 \rightarrow m-2)-3\,\! pour m>2\,\!

et donc :

2 \rightarrow n \rightarrow m = A(m+2,n-3)+3\,\! pour n>2\,\!

(les cas n=1\,\! et n=2\,\! peuvent être considérés en posant A(m,-2)=-1\,\! et A(m,-1)=1\,\!).


Nombre de Graham

Le nombre de Graham G\,\! — qui fut longtemps le plus grand nombre utilisé dans une démonstration mathématique — ne peut pas être exprimé de façon succincte dans la notation de Conway, mais si l'on définit la fonction f(n)=3\rightarrow 3\rightarrow n\,\!, alors :

  • G=f^{64}(4)\,\! et
  • 3\rightarrow 3\rightarrow 64\rightarrow 2 < G < 3\rightarrow 3\rightarrow 65\rightarrow 2\,\!

Il est possible de prouver le deuxième point :

3\rightarrow 3\rightarrow 64\rightarrow 2\,\!

= 3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (\ldots 3\rightarrow 3\rightarrow (3\rightarrow 3)\rightarrow 1\ldots )\rightarrow 1)\rightarrow 1\,\! (3), avec 128 fois le chiffre 3
= 3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (\ldots 3\rightarrow 3\rightarrow (3\rightarrow 3)\ldots ))\,\! (1)
= f^{64}(1)\,\!

De même, 3\rightarrow 3\rightarrow 65\rightarrow 2 = f^{65}(1) = f^{64}(27)\,\!

Comme f\,\! est strictement croissante, f^{64}(1) < f^{64}(4) < f^{64}(27)\,\!, ce qui conduit à l'inégalité recherchée.

On peut noter que la simple expression 3\rightarrow 3\rightarrow 3\rightarrow 3\,\! est immensément plus grande que le nombre de Graham.

Voir aussi


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Notation des flèches chaînées de Conway de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

  • Notation des fleches chainees de Conway — Notation des flèches chaînées de Conway La notation des flèches chaînées de Conway est un moyen d exprimer de très grands nombres créée par le mathématicien John Horton Conway. Elle consiste en une suite finie d entiers positifs séparés par des… …   Wikipédia en Français

  • Notation des flèches chaînées de conway — La notation des flèches chaînées de Conway est un moyen d exprimer de très grands nombres créée par le mathématicien John Horton Conway. Elle consiste en une suite finie d entiers positifs séparés par des flèches, comme par exemple . Comme… …   Wikipédia en Français

  • Notation des flèches de Knuth — En mathématiques, la notation des puissances itérées de Knuth est une notation qui permet d écrire de très grands entiers et qui a été introduite par Donald Knuth en 1976. L idée de cette notation est basée sur la notion d exponentiation répétée …   Wikipédia en Français

  • Notation de Conway — Notation des flèches chaînées de Conway La notation des flèches chaînées de Conway est un moyen d exprimer de très grands nombres créée par le mathématicien John Horton Conway. Elle consiste en une suite finie d entiers positifs séparés par des… …   Wikipédia en Français

  • Flèche chaînée de Conway — Notation des flèches chaînées de Conway La notation des flèches chaînées de Conway est un moyen d exprimer de très grands nombres créée par le mathématicien John Horton Conway. Elle consiste en une suite finie d entiers positifs séparés par des… …   Wikipédia en Français

  • John Horton Conway — Pour les articles homonymes, voir Conway. John Horton Conway John Horton Conway en 2005 Naissance 26& …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Liste Des Grands Nombres — En mathématiques, grand nombre n a pas de sens bien défini[1]. Liste de grands nombres finis 10100 est le gogol (101 chiffres) est le gogolplex (un 1 avec 10100 zéros) …   Wikipédia en Français

  • Liste des grands nombres — En mathématiques, grand nombre n a pas de sens bien défini[1]. Liste de grands nombres finis 10100 est le gogol (101 chiffres) est le gogolplex (un 1 avec 10100 zéros) …   Wikipédia en Français

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”