Le calcul de certaines suites de nombres peut parfois provoquer des envolées numériques au comportement étonnant, qui semblent filer vers des espaces intersidéraux infinis… mais qui peuvent éventuellement, contre toute attente, revenir atterrir tout doucement sur Terre!
Commençons tout d’abord par des « vols numériques » apparemment simples et qui paraissent à coup sûr revenir sur Terre, mais sans qu’on sache pourquoi au juste.
Le problème de Collatz
Le problème suivant (parfois appelé problème de Collatz) fait partie du « folklore mathématique ».
Partez d’un naturel $x$ quelconque. Si $x$ est pair, calculez $x ÷ 2$; sinon, faites $3x + 1.$ Et recommencez avec le nouveau nombre ainsi obtenu.
À priori, le comportement de telles suites de nombres paraît imprévisible. Cependant on observe qu’au cours des itérations successives, même si les nombres obtenus à la queue leu leu peuvent osciller en atteignant parfois des hauteurs insoupçonnées, les vols « à la Collatz » semblent tous finir par se poser sur la valeur 1. Et dès lors, le calcul boucle indéfiniment sur le cycle « 4, 2, 1 ». Ainsi, partant de 17, on obtient la suite de nombres:
\[52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1\]
Le vol 71 est nettement plus long (sa durée dépasse une centaine d’itérations) et passe même par l’altitude maximale 9 232, mais là encore il revient se poser en 1.
L’atteinte de 1 dans les suites numériques du type « $3x+1$ » a été vérifiée concrètement pour tous les $x$ jusqu’à l’ordre du trillion (un milliard de milliards, c’est-à-dire 1018), mais le problème de Collatz demeure à ce jour « ouvert », en ce sens qu’on ne dispose pas présentement de preuve générale, s’appliquant à toute valeur de $x,$ que le vol $x$ atterrit immanquablement en 1. Il ne s’agit donc encore que d’une conjecture.
En utilisant le tableur Excel, on peut facilement décrire le vol $x,$ pour un $x$ donné. Le tableau suivant donne quelques exemples de vols de Collatz.
Suites de Collatz sur Excel
Instructions
- Ouvrir une feuille Excel et sélectionner la cellule A5. Écrire « 115 » et valider en enfonçant la touche Entrée.
- La cellule A6 devrait maintenant être sélectionnée; définir le test logique suivant:
=SI(A5=PAIR(A5);A5/2;3*A5+1)
Valider en enfonçant la touche Entrée.
- Sélectionner la cellule A6 et amener le curseur sur le coin inférieur droit de la cellule. Le curseur change alors de forme. Enfoncer le bouton de la souris et, en le maintenant enfoncé, glisser jusqu’à la cellule A49, puis relâcher le bouton de la souris. Excel copie alors la définition du test dans chacune des cellules en incrémentant et donne la suite de Collatz du nombre 115. On constate que la suite se stabilise en donnant le cycle « 4, 2, 1 ». En changeant le nombre de la cellule A5, les calculs s’effectuent automatiquement. Si la suite est trop longue, et ne se stabilise pas dans les cellules A5 à A49, sélectionner la dernière cellule de la colonne et refaire l’incrémentation.
Commentaires
À l’étape 2, on définit un test logique de la forme:
= SI (test; valeur si vrai; valeur si faux)
Le test consistait ici à comparer le nombre inscrit en A5 et la valeur PAIR(A5). La fonction PAIR(·) a pour effet de calculer le plus petit nombre pair supérieur ou égal à son argument. Si on a A5 = PAIR(A5), cela signifie que le nombre en A5 est pair; dans un tel cas, le test indique au logiciel de diviser le nombre par 2 et d’inscrire le résultat en A6. Si A5 ≠ PAIR(A5), le test indique au logiciel d’écrire dans la cellule A6 le résultat de l’opération 3*A5+1.
Vous pouvez sélectionner l’ensemble des cellules de A5 à A49 (ou plus) et amener le curseur sur le coin inférieur droit de la dernière cellule (A49 ou autre). Le curseur change alors de forme. Enfoncer le bouton de la souris et, en le maintenant enfoncé, glisser la souris vers la droite. En changeant le nombre sur la première ligne des colonnes ajoutées, vous pouvez faire afficher la suite de Collatz de différents nombres.
Les suites de Goodstein
Après les vols numériques du type « Collatz », voici ceux « à la Goodstein ». Ces vols ont un comportement maintenant bien connu, mais qui demeure hautement étonnant, voire totalement contraire à l’intuition. Il y a une soixantaine d’années, le logicien anglais Reuben L. Goodstein (1912–1985) a en effet utilisé l’écriture des naturels selon diverses bases afin d’introduire des suites de nombres pour le moins étranges.
L’écriture d’un nombre en base $b$ revient à en faire un développement sous forme de somme de puissances de cette base (et de multiples de ces puissances).
Ainsi, en base dix, la notation 1 948 est une abréviation pour l’expression:
\[1\cdot 10^3 + 9\cdot 10^2 + 4\cdot 10^1 + 8\cdot 10^0.\]
Développement de 1 948 en puissances de 2.
En base cinq, ce même nombre a pour développement:
\[3 \cdot 5^4 + 0\cdot 5^3 + 2\cdot 5^2 + 4\cdot 5^1 + 3\cdot 5^0,\]
ce qui peut s’écrire (30 243)cinq de façon abrégée. La représentation en base deux correspond à des développements souvent fort longs, mais permet une notation dans laquelle n’interviennent que les deux chiffres 0 et 1, associables aux deux seules valeurs possibles pour un bit informatique. Ainsi, 10 948 correspond au développement figurant ci-dessus.
Ce développement donne la notation
(110 1100 0110 100)deux.
Goodstein a recours à une représentation complète d’un naturel en base b: il s’agit de partir du développement de ce naturel en base b, puis d’écrire comme une somme de multiples de puissances de b les exposants eux-mêmes que l’on rencontre dans ce développement, puis les exposants de ces exposants, etc., jusqu’à ce que la représentation devienne stable. Par exemple, dans le cas de 1 948, le terme $2^{10}$ devient successivement $2^{2^{3}+2},$ puis $2^{2^{2+1}+2}.$ La représentation complète en base deux de 1 948 est donnée ci-dessous.
Développement complet de 1 948 en puissances de 2.
La procédure de Goodstein consiste, étant donné la représentation complète de n en base b, à remplacer systématiquement b par b+1, puis à soustraire 1 du résultat ainsi obtenu. On obtient alors un nouveau naturel, auquel on peut appliquer le même processus, remplaçant cette fois b+1 par b+2 puis soustrayant à nouveau 1 (voir encadré ci-dessous). Et ainsi de suite, le « vol » se terminant si jamais on atterrit en 0. Comme le montre l’exemple de l’encadré, la croissance des hauteurs atteintes lors d’un vol à la Goodstein paraît très rapide et on semble se diriger vers des altitudes de plus en plus grandes. Le phénomène est encore plus frappant si on considère le vol 1 948: les premières altitudes sont successivement d’ordre de grandeur:
103, 1040, 10618, 1010 924, 10217 837, 104 871 827,
ce gigantisme de plus en plus époustouflant semblant devoir se poursuivre indéfiniment. On semble clairement en route vers des espaces sans bornes et les vols de Goodstein ne se termineraient donc jamais. Une telle observation est tout à fait en harmonie avec l’intuition: après tout, le procédé de Goodstein fait intervenir des tours d’exposants aux valeurs de plus en plus grandes, en comparaison desquelles la petite soustraction « -1 » paraît bien insignifiante.
Et pourtant… et pourtant, Goodstein a démontré que toute suite de Goodstein atteint 0. Voilà un résultat, il faut le reconnaître, on ne peut plus étonnant! Ainsi, un vol selon les règles de Goodstein correspond à une situation d’une complexité inouïe, mais qui relève d’un processus fini, qui se termine forcément après un certain temps — quoique extrêmement long! Le calcul des différentes étapes d’un vol de Goodstein est donc en général une tâche proprement colossale, mais qui aboutit néanmoins.
Il y a preuve. . . et preuve!
Il n’est pas facile d’expliquer en termes simples le comportement étrange des suites de Goodstein. On peut cependant signaler que si la partie exponentielle du processus de Goodstein semble provoquer une véritable explosion numérique, celle-ci n’en demeure pas moins restreinte d’un certain point de vue, la croissance illimitée n’étant qu’apparente. À la longue, la soustraction de l’unité en viendra à gruger les nombres colossaux auxquels on fait face. La plausibilité d’une telle éventualité peut ressortir à l’examen d’une suite de Goodstein remarquablement courte, la suite commençant à 3 qui est donnée ci-dessous.
On voit bien que le terme $g_2(3) = 3 \cdot 4^0$ étant en quelque sorte indépendant de la base 4, les termes suivants échappent aux changements successifs de base et la suite décroît alors tout bonnement vers 0 par applications répétées du « -1 ». Et le fait remarquable est que ce phénomène finira inévitablement par se produire, quel que soit le nombre de départ, le « -1 » finissant par grignoter entièrement, mais bien lentement, toutes les tours d’exposants. Certaines étapes de calcul augmentent parfois le nombre de termes dans les représentations complètes que l’on manipule (voir le calcul de $g_4(10)$ dans l’encadré de la page 21), mais les exposants alors en cause diminuent de valeur.
Le vol 3 (selon les règles de Goodstein) a une durée exceptionnellement courte. En effet, le simple passage au vol 4 provoque une explosion des plus spectaculaires: la durée de ce vol, avant l’atterrissage en 0, grimpe à $3 \cdot 2^{402 653 211} – 3$ itérations, ce qui n’est pas peu ! Et l’effet est encore plus saisissant si le vol se fait à partir d’un naturel plus grand.
Kurt Gödel
(1906–1978)
Les êtres mathématiques étant par nature abstraits, les connaissances en mathématiques, contraire-ment à d’autres sciences, se situent au-delà de la démarche expérimentale. Le savoir mathématique repose de manière essentielle sur la notion de preuve, d’argument valide à partir d’un ensemble initial de principes premiers, connus sous le nom d’axiomes. La nature et le rôle du raisonnement formalisé, tel qu’utilisé en mathématiques, s’avèrent depuis fort longtemps des sujets épineux, tant pour mathématiciens que philosophes. Le logicien Kurt Gödel a apporté une contribution fondamentale à ces réflexions en montrant que, contrairement à ce que pour- rait suggérer une perception naïve, les notions de vérité et de démontrabilité ne sont pas forcément équivalentes. Une telle équivalence peut certes se rencontrer dans certains contextes spécifiques et importants — ainsi, Gödel a établi, dans sa thèse de doctorat présentée à l’Université de Vienne en 1929, la complétude de la logique du premier ordre, montrant que les propositions qui sont démontrables dans un tel cadre sont précisément les propositions universellement vraies. Mais ce phénomène n’est pas du tout général. L’exemple type donné par Gödel où le vrai et le démontrable ne coïncident pas est celui de l’arithmétique élémentaire dans les nombres naturels: Gödel a construit un énoncé vrai à propos des naturels, mais indémontrable dans ce cadre formel. Par ses célèbres théorèmes d’incomplétude, obtenus en 1931, Gödel a marqué de façon profonde la philosophie des mathématiques et l’épistémologie des sciences. Les résultats de Gödel mettaient en effet fin à tout espoir d’identifier des prémisses sur lesquelles toutes les mathématiques pourraient être fondées axiomatiquement. Il en résulte que les mathématiques ne peuvent se ramener à la simple application de règles fixes. Autrement dit, un ordinateur — ou une machine de Turing (voir p. 30) — ne pourra jamais être programmé de manière à répondre à toute question d’ordre mathématique!
Aprés avoir occupé un poste à l’Université de Vienne au cours des années 1930, Gödel a émigré aux États-Unis en 1940. Il a fait carrière à l’Institute for Advanced Study de Princeton, où il avait notamment Einstein comme collègue de travail. Vers la fin de sa vie, il avait développé une peur paranoïaque d’être empoisonné, et il est mort d’inanition.
Les logiciens Laurie Kirby et Jeff Paris ont établi au cours des annés 80 que la très, très lente convergence des suites de Goodstein vers 0 est intimement reliée au fait qu’il n’est pas possible, dans le cadre axiomatique appelé arithmétique élémentaire, de démontrer que tout vol de Goodstein atterrit forcément en 0. On est donc ici en présence d’une affirmation (« toute suite de Goodstein atteint 0 ») dont on sait qu’elle est démontrable — c’est là précisément le théorème dû à Goodstein — mais qui par ailleurs, par le résultat de Kirby-Paris, ne peut être démontrée dans le contexte particulier d’une théorie mathématique formalisée (l’arithmétique élémentaire), qui fournit pourtant l’environnement naturel pour l’étude de problèmes combinatoires tels le calcul des suites de Goodstein.
Le théorème de Goodstein est donc un véritable théorème mathématique, mais il n’est cependant pas démontrable dans une théorie formelle à laquelle il appartient naturellement. Nous nous retrouvons ainsi plongés au cœur même des fameux théorèmes d’incomplétude dus au logicien Kurt Gödel (1906–1978). Mais cela est une autre histoire. . .
Destination… la Terre?!
Les envolées numériques dont il a été ici question illustrent donc deux phénomènes fort différents. Il y a d’un côté les vols à la Collatz, pour lesquels l’expérience nous suggère qu’ils doivent tous atterrir en 1 — ce qu’on ne sait cependant pas démontrer. Et de l’autre les vols à la Goodstein, si clairement, sur le plan intuitif, en route vers des espaces infinis… mais qui se retrouvent finalement tous sur Terre, quoi qu’après un très long moment. Et ça, on sait le démontrer! Étrange pour le moins…
Un nombre assez impressionnant!
Le nombre $3\cdot 2^{402 653 211} – 3,$ qui est la durée du vol 4 (selon les règles de Goodstein), est de l’ordre de $10^{121 210 695}$ et comprend donc plus de 121 000 000 de chiffres dans l’écriture décimale usuelle. Si on écrivait ces chiffres à raison de 100 chiffres par ligne et de 50 lignes par page, cela donnerait un livre de plus de 24 000 pages! Notons qu’un tel vol est vraiment TRÈS long, car sa durée (au rythme, disons, d’une itération à chaque seconde) dépasserait nettement l’âge même de l’Univers: en se basant sur les mesures récemment effec- tuées par la sonde WMAP (Wilkinson Microwave Anisotropy Probe) de la NASA, on estime actuellement que le Big Bang remonte à environ 13,7 milliards d’années. Cela « ne donne » qu’environ $4,32 \times 10^{17}$ secondes depuis la naissance de l’Univers, ce qui serait infime comparativement à la durée du vol 4. Et que dire du vol 1 948…
Les preuves de Goodstein et de Kirby-Paris
Les preuves des résultats dont il est question ici sont assez techniques et requièrent de bonnes connaissances de logique mathématique. Pour démontrer son théorème, Goodstein utilise la théorie des nombres ordinaux infinis1, qui fournit un environnement plus riche que l’arithmétique élémentaire. La preuve du théorème de Goodstein repose sur le fait que toute suite de Goodstein peut être codée à l’aide d’ordinaux infinis qui sont strictement décroissants et, donc, doivent forcément atteindre 0. Quant au théorème de Kirby-Paris — à savoir que le théorème de Goodstein n’est pas démontrable en arithmétique élémentaire —, il utilise le fait que les calculs que l’on peut effectuer dans le cadre de l’arithmétique élémentaire ont une complexité limitée. Or, le calcul de la longueur d’une suite de Goodstein, avant d’atteindre 0, excède justement cette limite de complexité.
Vitesse d’échappement et vols de Goodstein
Lorsqu’on lance une fusée de la surface terrestre, elle est décélérée de 9,8 m/s à chaque seconde (cette décélération varie avec l’altitude). Pour que la fusée puisse se libérer de l’attraction terrestre et partir dans l’espace, elle doit avoir une vitesse de 11,2 km/s. On appelle cette vitesse la vitesse d’échappement; elle dépend de la constante de gravitation, de la masse de la planète et de son rayon. Si la vitesse de la fusée est inférieure à la vitesse d’échappement, l’attraction terrestre finira par l’arrêter et elle retombera sur Terre. Par comparaison, la vitesse d’échappement de Jupiter est de 59,5 km/s, et celle d’un trou noir est supérieure à la vitesse de la lumière, soit 300 000 km/s.
Imaginons une planète, que nous appellerons la planète de Goodstein, dont la vitesse d’échappement est infinie. Supposons de plus que, de cette planète, on lance une fusée à une vitesse initiale de 5 km/s, la vitesse de la fusée variant à chaque seconde selon les règles de Goodstein. Les vitesses successives de la fusée sont alors décrites par le vol 5 de Goodstein, donné en encadré à la page 24. La définition d’une suite de Goodstein entraîne qu’à partir d’un certain stade, la fusée est décélérée à chaque seconde de 1 km/s et qu’elle finira donc, après un trrrrrès long moment, par avoir une vitesse nulle.
La logique mathématique
La logique mathématique est la branche des mathématiques où celles-ci sont considérées selon le point de vue du formalisme dont on se sert pour « faire des mathématiques ». Prenant ses origines dans les travaux des philosophes grecs — en particulier Aristote — sur la recherche systématique de formes correctes de raisonnement, la logique mathématique a été véritablement pressentie par Leibniz (1646–1716). On retrouve en effet chez lui l’idée de créer un langage formalisé doté de règles de déduction appropriées: c’est ce qu’exprime son projet de construction d’une langue caractéristique universelle (lingua characteristica universalis), système symbolique permettant l’élaboration d’un calcul du raisonnement (calculus ratiocinator) applicable à tout le champ de la pensée. Il a fallu attendre le milieu du XIXe siècle pour voir le premier développement d’une logique symbolique telle que suggérée par Leibniz, d’abord avec les travaux de Boole puis ceux de Frege et de Russell. Mais les résultats limitatifs obtenus, au cours de la décennie 1930, par Gödel, Church et Turing sont venus mettre un terme au projet formulé par Leibniz: la mécanisation complète du raisonnement est impossible. L’étude de raisonnements pouvant être effectués dans divers contextes formels demeure aujourd’hui encore au cœur même des travaux de recherche en logique mathématique. Cet intérêt se manifeste notamment dans les nombreuses applications de la logique mathématique en informatique, en particulier en intelligence artificielle et en robotique. Le champ de la logique mathématique s’est cependant étendu à d’autres domaines où le formalisme joue un rôle important. C’est le cas entre autres de tout ce qui concerne les questions de calculabilité, c’est-à-dire l’étude de ce qui peut être « calculé » (à l’aide d’automates, des machines de Turing, etc.)2, et ce, non seulement d’un point de vue théorique, mais également sur le plan pratique (on s’intéresse alors à la complexité des calculs). On peut ainsi établir l’existence de « fonctions non calculables », c’est-à-dire de fonctions clairement définies mais telles qu’aucun ordinateur, si puissant soit-il, ne pourra jamais les évaluer. Ou encore de « résultats indécidables », tels que les méthodes mathématiques traditionnelles ne soient pas en mesure d’en déterminer la véracité. (Par exemple, la conjecture « tout x atterrit à 1 », pour une certaine généralisation assez directe du problème de Collatz, s’avère justement être indécidable.) Et on rencontre aussi des « théorèmes non démontrables » qui, tel le théorème de Goodstein, ne peuvent être prouvés dans un contexte formel particulier.
Pour en s\(\alpha\)voirplus !
Sur le problème de Collatz
Un excellent article de vulgarisation sur le sujet:
DELAHAYE, Jean-Paul. « La conjecture de Syracuse » dans Pour la Science n° 247, mai 1998, p. 100–105.
Le texte suivant fait un survol très complet du problème de Collatz:
LAGARIAS, Jeffrey C. « The 3x+1 problem and its generalizations » dans The American Mathematical Monthly, n° 92, 1985, p. 3–23.
On trouvera sur le cybersite www.ieeta.pt/~tos/3x+1.html notamment un calculateur de suites du type « 3x+1 ».
Sur les suites de Goodstein
L’article technique dans lequel Kirby et Paris ont présenté leurs résultats sur les suites de Goodstein:
KIRBY, Laurie et Jeff PARIS. « Accessible independence results for Peano arithmetic » dans Bulletin of the London Mathematical Society, n° 14, 1982, p. 285–293.
On trouvera des exposés de vulgarisation sur les suites de Goodstein dans les deux textes suivants:
HODGSON, Bernard R. « Tâches herculéennes ou sisyphéennes? Un regard neuf sur le phénomène d’incomplétude en logique mathématique » dans PALLASCIO Richard et Gilbert LABELLE, Mathématiques d’hier et d’aujourd’hui, Modulo éditeur, 2000, p. 62–68.
DE KONINCK, Jean-Marie et Bernard R. HODGSON. « Ces nombres qui nous fascinent » dans PALLASCIO Richard et Gilbert LABELLE, Mathématiques d’hier et d’aujourd’hui, Modulo éditeur, 2000, p. 69–90.
Le fait que la suite de Goodstein commençant à 4 requiert 3 × 2402 653 211 – 3 étapes pour atteindre 0 n’est pas très difficile à établir et fait l’objet d’un exercice guidé dans :
HENLE, James M. An Outline of Set Theory, Springer-Verlag, 1986.
Sur le logicien Kurt Gödel et ses fameux théorèmes
Il existe plusieurs biographies de Kurt Gödel ainsi que de nombreux ouvrages — certains techniques et d’autres de vulgarisation — sur ses travaux de logique mathématique. Il convient de signaler un numéro spécial de la revue Pour la Science entièrement consacré à Gödel et à sa contribution aux mathématiques:
GUERRERIO, Gianbruno. « Gödel » dans Pour la Science, collection « Les génies de la science », n° 20, août 2004.
- Voir L’infini, c’est gros comment? ↩
- Voir Apprendre à parler à des machines, p. 26-30. ↩
