L’Explication de Leibniz à l’Académie royale des sciences (1703)

5L’origine de l’Explication de Leibniz remonte à quelques années avant 1703, lors d’échanges épistolaires qu’il entretient avec le duc de Brunswick (1735-1806) ; dans une lettre datée de 1697, Leibniz adresse au duc un médaillon sur lequel sont représentés les nombres dans le système décimal et leur correspondance en binaire (jusqu’à 16)3. Il insiste sur l’harmonie qu’il existe dans la façon de générer les nombres en répétant des motifs et sur la symétrie qu’on peut observer dans les suites de 0 et de 1 (Glaser 1981 : 31). Il adresse ensuite deux lettres à Christian Schulenburg, recteur de l’école de la cathédrale de Brême, en 1698, dans lesquelles il introduit la notation binaire (sans toutefois utiliser les puissances de 2 explicitement, seulement les nombres 1, 2, 4, 8, 16, 32, etc.) et présente la table des multiples de 3 avec leurs représentations en binaire, comme le montre le tableau ci-dessous.

Leibniz remarque alors plusieurs choses : dans un premier temps, chaque colonne a une période caractéristique. Par exemple, la colonne constituée des chiffres des unités de la liste en question (la 1^ère colonne à droite) révèle la période 01 ; la seconde 0110 ; la troisième 00101101, etc. Il remarque également que la période de la n-ième colonne (en partant de la droite) est de taille 2ⁿ et enfin que la seconde moitié de chaque période est obtenue en prenant le symétrique de la première moitié de la période, c’est-à-dire en transformant les 1 en 0 et vice-versa (Glaser 1981 : 33). Leibniz continue d’échanger à ce sujet avec le mathématicien Jean Bernoulli (1667-1748) en 1701, ce dernier identifiant clairement la position des 0 et des 1 dans l’écriture binaire avec les puissances de 2 correspondantes. C’est à l’issue de cet échange que Leibniz, alors âgé de 57 ans, adresse son Explication à l’Académie des sciences, qui aura un certain impact au sein de la collectivité scientifique (Glaser 1981 : 39). En effet, dans le commentaire éditorial rédigé par Bernard le Bouyer de Fontenelle (1657-1757) suite à la publication de sa Nouvelle Arithmétique, ce dernier explique que l’arithmétique binaire présentée par Leibniz n’avait pas été incluse dans l’Histoire de l’Académie Royale des Sciences avant qu’il n’y trouve une application « concrète » : l’interprétation des figures chinoises de Fohi, premier empereur mythique de la Chine (Glaser 1981 : 43).

6Les figures chinoises en question représentent un ensemble de soixante-quatre diagrammes composés de lignes pleines – et de lignes discontinues − −. Elles se trouvent dans un ouvrage intitulé Yi-jing, traité cosmologique occupant une place fondamentale dans l’histoire de la pensée chinoise, élaboré durant le I^er millénaire avant notre ère.

Dans le diagramme du Yi-jing, les lignes pleines représentent les Yang et les lignes discontinues représentent les Yin. En considérant les lignes pleines comme des 0 et les lignes discontinues comme des 1, apparaît alors l’analogie entre les soixante-quatre diagrammes du Yi-jing et la représentation en binaire des 64 premiers nombres entiers (Zhonglian 2000 : 165). Leibniz aurait alors formalisé le système binaire grâce aux échanges entretenus avec le père jésuite et missionnaire français Joachim Bouvet (1656-1732), ce dernier ayant immédiatement fait le rapprochement entre l’arithmétique de Leibniz et les hexagrammes chinois. Leibniz se serait alors inspiré du système binaire pour illustrer sa philosophie duale (et également pour promouvoir son idée d’écriture universelle) et le fait que tout phénomène du monde physique peut être expliqué sur l’hypothèse de deux forces opposées (1 = Dieu, 0 = le vide). Mais le principal usage que Leibniz voulait faire de la numération binaire était son application à la découverte des propriétés des nombres, car en fournissant l’expression la plus simple des nombres, elle devait révéler des propriétés plus ou moins manifestes dans d’autres systèmes, comme des propriétés de périodicité.

7Dans son commentaire éditorial de 1703, de Fontenelle précise que l’arithmétique binaire a été inventée au même moment par quelqu’un d’autre : Thomas Fantet de Lagny (1660-1734). Lagny est professeur d’hydrographie à Rochefort, il intègre l’Académie des sciences en 1695 et contribue fréquemment aux Mémoires par la publication d’ouvrages et de notes sur des sujets scientifiques. Ses recherches portent sur la navigation et il développe dans ce contexte une nouvelle trigonométrie qui l’amène à remédier à certains problèmes par la numération binaire, dont l’avantage majeur est de simplifier considérablement les multiplications et les divisions (Glaser 1981 : 44-45).

Mais M. de Lagni prétend que cet avantage que la théorie promet si magnifiquement, se réduit à rien dans la pratique ; qu’au contraire comme les logarithmes […] il y a toujours plus de chemin à faire, quoique peut-être plus facilement […]. (Fontenelle 1703 : 62)

Les travaux antérieurs de Thomas Harriot (1560-1621)

8Un autre personnage souvent oublié de l’histoire de la numération binaire, réhabilité par John Shirley en 1951, est le mathématicien et astronome anglais Thomas Harriot (1560-1621). Ce dernier analysa plusieurs systèmes de numération de position : le binaire, le ternaire, le quaternaire, le quinquénaire, ainsi que des systèmes de numération à bases plus élevées. Ses manuscrits non publiés, qui contiendraient plusieurs milliers de pages (Glaser 1981 : 11), se trouvent actuellement au British Museum et un certain nombre de feuillets montrent la clarté avec laquelle il expose le système binaire, ainsi que les opérations élémentaires qu’il est possible d’effectuer (Shirley 1951 : 453). Il commence par présenter un tableau avec la liste des premiers entiers naturels de 1 à 31 suivis de leur décomposition en puissances de 2 (sans toutefois faire usage de l’exposant, comme Leibniz, par exemple 15 | 8 + 4 + 2 + 1). Viennent ensuite des tableaux permettant de dénombrer les combinaisons de n éléments (pour n allant de 1 à 5) en utilisant des lettres. Par exemple, les combinaisons possibles d’au plus 3 éléments a, b, c sont : a, b, c, ab, ac, bc, abc, ce qui donne en tout 7 combinaisons. Il y a en une pour un ensemble à 1 élément, noté (a), il y en a trois pour un ensemble à 2 éléments, notés (a, b, ab), il y en quinze pour un ensemble à 4 éléments, notés (a, b, c, d, ab, ac, ad, bc, bd, cd, abc, abd, acd, bcd, abcd) et trente-et-un pour un ensemble à 5 éléments (Glaser 1981 : 11-12).

Afin d’énumérer systématiquement toutes les combinaisons possibles, Harriot développe une technique en colonne en utilisant les signes + et −. Le signe + signifie qu’on inclut la lettre dans la combinaison (la première colonne pour la lettre a, la deuxième pour b et la troisième pour c) et le signe – qu’elle n’est pas incluse. Toujours avec l’exemple de trois éléments, on obtient :

La première ligne, ne comprenant que des signes –, correspond au vide et représente le nombre 0 qui ne compte pas dans le dénombrement des combinaisons, mais constitue une sorte de point de départ à partir duquel on décline ensuite les symboles + et − pour retrouver l’ensemble à 7 combinaisons {a, b, c, ab, ac, bc, abc} (Glaser 1981 : 12). Harriot réordonne ensuite cette colonne de signes de manière à les générer plus facilement :

Harriot ne fournit que le tableau de signes pour générer les combinaisons d’ensembles à 1, 2, 3, 4 et 5 éléments et généralise son idée par un « etc. » qui, selon Glaser, montrerait qu’il aurait compris le théorème selon lequel il y a 2 ⁿ − 1 combinaisons (non vides) d’un ensemble à n éléments. De même pour le fait que les entiers de 1 à 2 ⁿ − 1 peuvent s’exprimer comme somme des nombres 1, 2, 4, 8, 16, etc. Par ailleurs, d’autres pages de ses manuscrits montrent explicitement qu’il connaissait la base binaire ; il fournit des exemples où il transcrit des nombres décimaux en binaire et procède à des opérations (addition, soustraction, multiplication, division) avec eux, voir (Glaser 1981 : 14) (Shirley 1951 : 453).

9Selon Shirley, aucun manuscrit mathématique antérieur à celui de Harriot ne montre d’intérêt similaire pour cette théorie abstraite des nombres, et la non réception de son travail montre également que ses contemporains ne s’en souciaient guère. Harriot n’a pas cherché à trouver une application concrète pour justifier le système qu’il a développé (contrairement à Leibniz qui en un sens justifie sa découverte avec des considérations métaphysiques) et l’a donc mis de côté (Shirley 1951 : 454). Ce fut également le cas pour l’abbé espagnol Juan Caramuel y Lobkowitz (1606-1682) qui consacre deux pages et demie à l’arithmétique binaire (ainsi qu’à d’autres systèmes de numération) dans un écrit de 1670, restées inconnues de ses contemporains.

La reconnaissance de l’intérêt du système binaire (fin du xviii^e siècle)

10C’est à la fin du xviii^e siècle et au xix^e siècle que l’intérêt du système binaire est reconnu, d’abord pour des raisons économiques et politiques (unifications des systèmes de mesure), notamment en France et en Angleterre par les mathématiciens Adrien-Marie Legendre (1752-1833), Peter Barlow (1776-1862) et Auguste De Morgan (1806-1871). Dans ce contexte, on observe un intérêt marqué pour le système binaire et des discussions portant sur l’utilisation d’autres numérations que la numération décimale sont dans l’air du temps ; en 1790, la commission métrique française, composée de scientifiques comme Joseph-Louis Lagrange (1736-1813), Antoine Lavoisier (1743-1794), Antoine de Condorcet (1743-1794) et d’autres, se réunit et propose à l’Académie des sciences d’adopter le système duodécimal pour le système métrique. Mais cela nécessitait de l’adopter également pour le système de poids, pour garder une certaine cohérence, et Lagrange refuse, ne voyant aucun apport théorique à l’utilisation de la base 12 (Glaser 1981 : 171). En 1857, l’inventeur britannique Isaac Pitman (1813-1897) s’oppose farouchement à l’adoption du système décimal pour les poids et les mesures préférant de loin le système duodécimal. En 1862, l’ingénieur civil américain John William Nystrom (1825-1885) propose d’adopter le système de numération en base 16, puis en base 12, refusant clairement le système décimal pour les poids et les mesures, tout comme Napoléon dans ses mémoires. La Grande-Bretagne sera le dernier grand pays à légaliser l’utilisation optionnelle du système métrique dans le commerce en 1897 (Glaser 1981 : 171-172). Ces désaccords concernant le système de numération qui présenterait le plus d’avantages pour une utilisation quotidienne se traduisent également dans quelques textes de scientifiques de l’époque, comme le mathématicien et logicien britannique De Morgan ou l’astronome et statisticien danois Thorvald Thiele (1838-1910) qui s’interrogent sur l’apprentissage de ces systèmes et cherchent à trouver la base qui serait la plus facile à enseigner.

Le jeu de Nim (1901)

15Le jeu de Nim est analysé pour la première fois en 1901 par Charles Leonard Bouton (1869-1922), mathématicien et enseignant à Harvard, qui publie un article dans le journal Annals of Mathematics intitulé « Nim, a Game with a Complete Mathematical Theory » (Bouton 1901). Le jeu de Nim oppose deux joueurs, A et B, et se présente de la sorte : sur une table sont disposées trois rangées d’objets – disons des bâtonnets – chacune en contenant un nombre arbitraire et différent au début du jeu. À tour de rôle, les joueurs A et B sélectionnent une des rangées et retirent autant de bâtonnets qu’ils le souhaitent : un, deux,… ou la rangée entière (ils peuvent changer de rangée à chaque tour, ou jouer dans la même). Le gagnant est celui qui retire le(les) dernier(s) bâtonnet(s) de la table. La chose essentielle demeure la suivante : les bâtonnets ne sont retirés que d’une seule rangée, et au moins un bâtonnet doit être retiré. Dans son article, Bouton montre que si A, après avoir joué, laisse une certaine position de jeu à son adversaire, et qu’il ne commet ensuite aucune erreur, B ne peut pas gagner. La détermination de ces positions particulières, appelées par Bouton « safe combinations » (littéralement « positions sûres »), repose sur la traduction du nombre de bâtonnets de chaque rangée en… binaire ! Prenons par exemple la configuration initiale où il y a trois rangées contenant respectivement 3, 5 et 7 bâtonnets, comme le montre la figure 26.

Figure 26 : La position initiale d’une partie de jeu de Nim avec 3 rangées contenant respectivement 7, 5 et 3 bâtonnets.

Ces trois nombres décimaux transcrits en binaire donnent : 011, 101 et 111 (le 0 à gauche du premier nombre est inutile, mais servira pour la suite). Ensuite, comme Leibniz qui recherchait les périodes dans les colonnes des nombres écrits en binaire de la table de 3 ou de la liste des premiers carrés, Bouton explique qu’il faut placer les nombres binaires obtenus en colonne (en alignant bien les mêmes unités entre elles), puis qu’il faut sommer chaque colonne en binaire, sans tenir compte des retenues (ainsi, les seules règles à appliquer sont que 1 + 1 = 0 et 1 + 0 = 1). On obtient alors le résultat suivant, aujourd’hui appelé Nim-somme ou Nim-addition dans le vocabulaire mathématique de la théorie des jeux combinatoires8 :

Si le résultat de la somme de chaque colonne est égal à 0 (ce qui n’est pas le cas ici) alors la position en question est une position sûre pour le joueur qui vient de la jouer. L’idée est donc d’essayer de laisser à son adversaire une position dont la Nim-somme est nulle, car quoi qu’il joue par la suite, il nous laissera une position qui n’est pas une position sûre (dont la Nim-somme n’est pas nulle) et nous pourrons alors à nouveau lui laisser une position sûre. En reprenant l’exemple ci-dessus, la meilleure stratégie à adopter est de commencer la partie et de retirer un bâtonnet d’une des rangées. Cela aura pour conséquence de transformer un 1 en 0 dans la colonne de droite et rendre la Nim-somme nulle. Imaginons que nous enlevions un bâtonnet de la deuxième rangée (celle avec 5 bâtonnets). La position devient alors 3, 4, 7 qui donne en binaire : 011, 100, 111 (dont la Nim-somme est effectivement nulle). Si notre adversaire décide, par exemple, de retirer 6 bâtonnets de la troisième rangée, il reste alors la position 3, 4, 1 (dont la Nim-somme n’est pas nulle). Pour savoir quoi jouer pour se ramener à une position sûre, il faut commencer par traduire 3, 4, 1 en binaire : cela donne 011, 100, 001, dont la Nim-somme est 110. La seule possibilité pour transformer cette Nim-somme en 000, en n’agissant que sur une rangée (et sans augmenter le nombre de bâtonnets !), est de transformer la rangée 100 en 010, c’est-à-dire de passer de 4 à 2 bâtonnets. On obtient alors 3, 2, 1, ce qui donne 011, 010, 001 en binaire, dont la Nim-somme est nulle. Pour une analyse détaillée du jeu de Nim, de son histoire et de son utilisation en classe, voir (Rougetet 2016a) et (Pelay, Rougetet & Boissière 2017). Cette stratégie de résolution reste valable pour un nombre de rangées supérieur à trois et pour un nombre arbitraire de bâtonnets, on peut même supposer que certaines rangées contiennent une infinité de bâtonnets (Delahaye 2010). Le jeu de Nim peut également se présenter sous une forme simplifiée dans laquelle il n’y a qu’une rangée de bâtonnets, par exemple 20, les joueurs pouvant retirer alternativement un ou deux bâtonnets. Cette variante n’est autre que la course à 20 proposée par Guy Brousseau dans sa Théorie des situations didactiques (1998), mais en version soustractive, car on retire des bâtonnets plutôt que d’ajouter au fur et à mesure 1 ou 2 au résultat précédent pour atteindre 20 le premier.

16La publication de Bouton suscite de l’intérêt dans le milieu professionnel mathématique en Europe et aux États-Unis. Plusieurs publications dans des revues mathématiques présentent des variantes du jeu de Nim. En 1907, le mathématicien néerlandais Willem Abraham Wythoff (1865-1939), spécialiste de théorie des nombres, propose un jeu de Nim dans lequel il n’y a que deux rangées d’objets et les joueurs peuvent en retirer autant qu’ils veulent d’une rangée ou bien le même nombre dans les deux rangées (Wythoff 1907). En 1910, le mathématicien de l’université de Chicago Eliakim Hastings Moore (1862-1932), présente le Nim_k (lire « Nim indice k ») dans lequel il y a un nombre quelconque de rangées et les joueurs peuvent retirer les batônnets d’une seule ou de plusieurs rangées, sans excéder k rangées (Moore 1910). Les publications de ces résultats se font dans des journaux spécialisés de mathématiques : Wythoff publie dans Nieuw Archif voor Wiskunde, journal de l’Académie royale danoise de mathématiques et Moore dans The Annals of Mathematics. La circulation de l’analyse du jeu de Nim et de ses variantes permet la découverte de liens théoriques avec d’autres jeux. Par exemple, en 1935-1939, un important théorème est énoncé indépendamment par l’Allemand Roland Sprague (1894-1967) et le Britannique Patrick Grundy (1917-1959) pour généraliser la résolution de certains jeux combinatoires à partir de la solution fournie par Bouton en 1901. Pour un article centré sur le rôle du Nim de Bouton dans le développement de la théorie des jeux combinatoires, voir (Rougetet 2016b).

Les premières machines électromécaniques conçues pour jouer au Nim

17Au printemps 1940, une machine électromécanique destinée à jouer au jeu de Nim, le Nimatron, est inventée par deux employés des laboratoires de recherche de l’entreprise Westinghouse Electric durant leur pause déjeuner. Elle a été construite puis exposée au Westinghouse Building de New York durant une foire mondiale où elle a joué plus de 100 000 parties contre le public et gagné près de 90 000. La plupart des défaites du Nimatron ont eu lieu contre les organisateurs de l’exposition pour convaincre les gens que la machine pouvait être battue – ces derniers étaient persuadés du contraire… Le Nimatron était conçu pour jouer une partie de Nim de quatre rangées, chacune contenant au maximum sept jetons. Le succès du Nimatron a engendré la construction d’autres machines plus perfectionnées (la volonté première étant qu’elles prennent moins de place) et pouvant jouer à d’autres variantes du jeu de Nim. L’une d’elles a été conçue dans le département de mathématiques de l’université de Californie de Los Angeles par Raymond Redheffer (1921-2005) pour sa thèse de doctorat et, en 1951, l’entreprise britannique d’ingénierie électrique et d’équipement électronique Ferranti conçoit le Nimrod, premier ordinateur numérique destiné à jouer au jeu de Nim. Le Nimrod est exposé à un festival scientifique en Grande-Bretagne en mai 1951, puis pendant trois semaines à Berlin lors d’un salon industriel en octobre de la même année. Ces expositions publiques furent un réel succès, mais pas toujours dans le sens où les constructeurs l’entendaient : la plupart des gens étaient très impressionnés et restaient bouche bée devant les lumières clignotantes censées représenter l’activité pensante du Nimrod ! Rares sont les spectateurs qui s’intéressaient à l’algorithme – pourtant détaillé sur le côté de la machine – et persistaient à essayer de battre la machine. Les lecteurs curieux d’en apprendre davantage sur les aspects socioculturels du jeu de Nim et de ses variantes pourront consulter la thèse de (Rougetet 2014 : 293-324), ainsi que (Rougetet 2015) sur les machines à jouer des jeux combinatoires.

Au-delà des récréations mathématiques

18Les différents systèmes de numération ont joué un rôle dans les mathématiques récréatives ainsi que dans certains ouvrages consacrés à la théorie des nombres (Glaser 1981 : 118). Nous avons vu notamment qu’à partir du début du xx^e siècle avec le jeu de Nim et ses variantes, le système binaire intervient dans la conception de programmes, du fait même de sa présence dans la résolution du jeu de Nim. Avant cela, peu de récréations mathématiques font appel explicitement au système binaire – ou tout du moins présentent de manière claire les liens qu’elles entretiennent avec lui. Lucas fut l’un des premiers à avoir conçu une récréation, la Tour d’Hanoï, dont la résolution est fondée sur la numération binaire. Et bien évidemment avant cela, le baguenodier, dont les origines et les premières analyses remontent au moins au xv^e siècle (chapitre 8).

Mais l’application du système binaire à des situations « concrètes » ne s’est pas seulement faite dans le cadre de casse-têtes ou de récréations mathématiques dénichés par quelques mathématiciens voulant torturer les esprits de ceux qui les pratiquaient. On trouve d’autres exemples à travers l’Histoire de personnages ayant utilisé le système binaire (à la fois pour représenter, mais aussi pour calculer) et ses propriétés dans des approches très différentes, qui montrent la diversité des applications qui peuvent en être faites. Le philosophe anglais Francis Bacon (1561-1626) par exemple, l’emploie dans le cryptage de messages : à chacune des 24 lettres de l’alphabet (pas de v ni de j en anglais à cette époque), Bacon associe un code binaire – avec des a et des b – constitué de cinq caractères. Par exemple, le mot anglais flee (qui signifie « fuir ») se traduit aababababaaabaaaabaa dans le code de Bacon9 qui aurait tout à fait pu utiliser des 0 et des 1 à la place des a et des b. L’inventeur français Joseph Marie Jacquard (1752-1834), quant à lui, met au point des cartes perforées pour les métiers à tisser pour contrôler l’élévation ou non des chaînes tandis que les fils de trame passent à travers la machine pour fabriquer le tissu. Selon le code imprimé sur la carte, défini par les différents endroits où elle est perforée, le motif de tissage n’est pas le même. Dans une vision plus « théorique », le logicien et mathématicien britannique George Boole (1815-1864) définit une algèbre basée sur le binaire, cette dernière constituant aujourd’hui la base logique des ordinateurs. Du côté « pratique », l’ingénieur français Émile Baudot (1845-1903) met en évidence un code binaire particulier qui révolutionnera le domaine des télécommunications, notamment dans la réduction des erreurs lors de la transmission des messages, nous le verrons dans le chapitre 5.