Jeudi 12 Décembre 2024
Rechercher 🔍

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

Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.
- Introduction - Définition - Exemples - Propriétés - Nombre de Graham - Fonction d'Ackermann

Introduction

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 3\rightarrow 4\rightarrow 5\rightarrow 6 .

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.

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 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.

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 indique 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}\,\!

Propriétés
- Introduction - Définition - Exemples - Propriétés - Nombre de Graham - Fonction d'Ackermann
miniature
Découverte: la lumière transforme un isolant en métal 💡
miniature
Cet aliment à bannir nourrit les cancers 🍽️
miniature
Cette tablette de 3000 ans dévoile une écriture jusqu'alors inconnue ✍️
miniature
Découverte d'une chimie des océans refroidissant le climat 🌊
miniature
Le télescope James Webb, poussé à ses limites, découvre ces structures incroyablement anciennes 🔭
miniature
Le rôle surprenant de la grossesse contre la grippe A 🦠
miniature
Découverte d'une nouvelle espèce éteinte grâce à... un accélérateur de particules ⚛️
miniature
Une avancée prometteuse pour le déploiement des batteries sodium-ion 🔋
miniature
Voici comment et pourquoi le risque de cancer augmente... puis diminue avec l'âge 🧬
miniature
Le Soleil bientôt en "zone de combat": une période de turbulences extrêmes ☀️
miniature
1
Les rhumatismes plus douloureux par temps humide: vrai ou faux ? 🌧️
miniature
Ce nouveau type de moteur repousse les limites du vol supersonique ✈️
miniature
Poster sur les réseaux sociaux peut nuire à votre santé mentale 🧠
miniature
Une super-Terre entre Mars et Jupiter ? 🌎
miniature
Découverte impressionnante d'un fossile de crocodile géant 🐊
miniature
1
Cet accident en laboratoire pourrait transformer drastiquement la mémoire numérique ⚡
miniature
1
Un virage technologique révèle l'impact du diabète gestationnel 🩺
miniature
Insolite: ces loups butinent des fleurs ! Des grands carnivores pollinisateurs ? 🌼
miniature
1
Ce fin gilet robotisé soulage les tâches répétitives 🦾
miniature
Les équations d'Einstein invalidées ? 👀
miniature
Ce tatouage électronique se connecte à votre cerveau 🧠
miniature
Cette IA de Google prédit la météo mieux que jamais, et sur 15 jours ! 🌦️
miniature
Des plats au bœuf... sans bœuf ? 🥩
miniature
2
Ce moteur de recherche d'un nouveau genre bouscule nos habitudes 🔍
miniature
Pourquoi les cheveux bouclent-ils en fonction de la météo ? 🌦️
miniature
Découverte: d'autres univers plus propices à la vie que le notre 👽
miniature
Ces sons urbains qui minent notre santé mentale 🚗
miniature
La testostérone impacte-t-elle vraiment le désir sexuel des hommes ? 🔥
miniature
Des microalgues éliminent les métaux lourds: voici comment 🧪
miniature
1
Et voici un qubit mécanique ! 🖥️
miniature
Les lentilles de contact sont-elles vraiment sans danger ? 👁️
miniature
Dans la course à l'IA générative, Google lance son générateur de vidéos 🎥
miniature
4
Une zone oubliée du cerveau permet aux paralysés de marcher à nouveau 🧠
miniature
Cette astuce quotidienne ajoute 11 ans à votre vie 🕒
miniature
Révolutions, migrations des européens... les éruptions volcaniques ont influencé l'histoire 🌋
miniature
Soit l'énergie noire n'est pas constante, soit une seconde force inconnue est à l'œuvre... 🌀
miniature
Voici pourquoi l'alcool peut rendre agressif 🥂
miniature
Expérience inédite: ce laser projette une ombre visible 💥
miniature
Ce plat millénaire réduit significativement la graisse corporelle 🍽️
miniature
Les scientifiques trompés ? La Voie Lactée n'est PAS comme les autres galaxies 🔭
miniature
Pourquoi ce que pensent les autres de nous nous fait tant ruminer ? 🧠
miniature
De la vie découverte sur un échantillon de l'astéroïde Ryugu (oups) 👽
miniature
2
Des anomalies incompréhensibles de températures détectées simultanément presque partout sur Terre 🌡️
miniature
Cette planète, trop jeune pour exister, bouscule les lois de l'astronomie 🪐
miniature
Une montagne d'or découverte en Chine ⛏️
miniature
Cette simulation de l'Univers est totalement vertigineuse 🌀
miniature
1
Une pilule pourrait-elle imiter les bienfaits du yoga ? 🧘
miniature
Nous serions-nous trompés sur l'origine de l'écriture alphabétique ? ✍️
miniature
Voici pourquoi votre enfant triche et ce que cela révèle 🧠
miniature
Le Sahara verdit, et cela pourrait bien (re)changer notre climat 🌱
Page générée en 0.226 seconde(s) - site hébergé chez Contabo
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
A propos - Informations légales | Partenaire: HD-Numérique
Version anglaise | Version allemande | Version espagnole | Version portugaise