David Madore's WebLog

2008-03-28 (vendredi)

Annonce de congrès

L'édition d'il y a deux ans ayant été un grand succès, nous avons décidé de rééditer cette année — mardi, pour être exact — un congrès en l'honneur de Sophie Germain et à l'occasion de son anniversaire. L'annonce du congrès se trouve ici, et nous espérons vous y voir nombreux.

Note : la deadline pour les propositions d'exposés est fixée à une date indéterminée : il est donc encore temps d'écrire aux organisateurs si vous pensez pouvoir intervenir sur le thème proposé, n'hésitez pas à nous écrire.

Commentaires

2008-03-27 (jeudi)

Une hydre à combattre : première partie (petit jeu informatique)

Alors que j'étais terrassé par un puissant rhume pendant le week-end de Pâques, j'ai réalisé cette page — que ce n'est même pas la peine d'aller voir si vous n'avez pas un navigateur Web moderne (je pense qu'il n'y a à peu près que les Firefox, Opera et peut-être certains Safari qui arriveront à l'afficher correctement ; notamment, si vous ne voyez pas s'afficher un rectangle gris avec des segments verts et marron, c'est qu'il vous manque le support SVG ou JavaScript — et si vous ne voyez même pas le titre correct, c'est que votre navigateur ne comprend pas le XHTLM). Avec beaucoup de clémence on pourrait qualifier ça de jeu (ou plutôt de time waster).

Vous incarnez Hercule, et votre but est de tuer l'hydre affichée sur la page. Celle-ci n'a, initialement, qu'une tête, au cou plus ou moins long (c'est-à dire reliée à son corps par l'intermédiaire de plusieurs segments, qui s'attachent en des nœuds), elle meurt quand elle n'a plus aucune tête, mais à chaque fois qu'on coupe une tête d'autres peuvent repousser selon des règles que je vais détailler. Pour jouer, Hercule n'a qu'à choisir la tête qu'il veut découper et cliquer dessus (il faut cliquer sur le gros point noir qui représente la tête) ; on ne peut couper qu'une tête, c'est-à-dire un nœud de l'hydre en bout de cou (qui n'a lui-même aucun descendant).

Les règles qui régissent la repousse des têtes dépendent du type de cou auquel la tête coupée était attachée. Notre hydre a deux types de segments : elle est plus puisante que l'hydre de Kirby-Paris qui n'en a qu'un seul, les normaux (mais si vous parvenez à terrasser l'hydre, vous passerez forcément par un stade où elle aura été réduite à cette version moins puissante).

• Les cous les moins embêtants sont les cous normaux (ils sont représentés en vert fin sur ma page). D'abord, si vous tranchez un cou normal qui est directement relié à la base de l'hydre (son corps, quoi), rien ne repousse — c'est d'ailleurs le seul cas où l'hydre n'a pas la posssibilité de se régénérer. Si vous tranchez un cou normal n'importe où ailleurs dans l'hydre, celle-ci a la possibilité de régénérer de nouvelles copies du nœud auquel ce cou était relié (le nœud « père » de la tête découpée) : c'est-à-dire reproduire non seulement le nœud lui-même et le segment qui le relie à son propre père (le « grand-père » de la tête découpée), mais aussi tous ses descendants (sauf le cou qui a été tranché, évidemment), et ce, en autant d'exemplaires que l'hydre le souhaite. Remarquez cependant que par cette opération l'hydre ne peut grandir qu'en largeur, jamais en hauteur.
• Les cous funestes (marron et épais sur ma page) sont beaucoup plus puissantes. Si vous tranchez un cou funeste, l'hydre a la faculté de régénérer, à la place de la tête tranchée, une copie d'un nœud situé plus près du corps de l'hydre. Précisément, on remonte depuis la tête tranchée vers le corps de l'hydre jusqu'à rencontrer un segment normal (et non funeste), et la totalité de la sous-hydre qui part de ce nœud pourra être reproduit à la place de la tête coupée. Mais il y a pire : l'hydre peut reproduire cela aussi profondément qu'elle le veut : à la place de la tête coupée apparaît une sous-hydre qui peut elle-même contenir une copie en abyme de la même sous-hydre et ainsi de suite jusqu'au niveau que l'hydre le souhaite. La seule bonne nouvelle, c'est que les copies sont attachées par des cous normaux (et non funestes).

Hum, voilà qui était un peu compliqué à dire, mais c'est en fait très simple et on comprend tout de suite les règles en jouant un peu avec mon programme. (Je vous invite à essayer, et si vous arrivez à exprimer les règles de façon plus concise et claire, faites-le moi savoir dans les commentaires !)

Par ailleurs, mon hydre est assez domestique : elle ne fait qu'un usage très modéré de son droit à repousser des têtes (souvent elle ne l'utilise même pas du tout), ne serait-ce que parce qu'il fallait bien que l'écran ne déborde pas trop, et un petit peu de patience suffit donc à la tuer (surtout si on ne choisit pas trop stupidement les têtes à couper). On a peut-être l'impression que si l'hydre était un peu plus méchante la tâche serait infinie (essayez par exemple de faire une copie locale du fichier et de remplacer les lignes 271–272 par var prob = 1./rep; — m'est avis que vous n'irez pas bien loin avec cette hydre-là) : que dire d'une hydre qui se répliquerait dix fois à la première tête coupée (si les règles lui permettent de se régénérer, bien sûr), cent à la suivante, mille ensuite ? Sûrement il serait impossible pour Hercule de la terrasser ! Ou peut-il y arriver en choisissant intelligemment les têtes à couper ? Car même avec mon hydre bien gentille, il faut une sacrée patience pour gagner en coupant, disons, toujours la tête la plus à gauche.

Le résultat mathématique est surprenant :

Aussi méchante que soit l'hydre dans sa volonté de se reproduire,
aussi stupide que soit Hercule dans le choix des têtes à couper,
Hercule finit toujour par gagner
(en temps fini).

En temps fini, ça ne veut pas dire rapidement : si l'hydre se reproduit dix fois puis cent fois puis mille fois et ainsi de suite (ou même, en fait, une fois puis deux puis trois et ainsi de suite), et si Hercule coupe à chaque fois la tête la plus à droite, il faudra un nombre d'étapes tellement grand pour finir que la fonction d'Ackermann du nombre de particules dans l'univers, en comparaison, c'est de la gnognote. Mais Hercule finit toujours par gager, quelle que soit la mauvaise volonté qu'il y mette et quels que soient les efforts de l'hydre pour faire sa mauvaise tête (pun unintended) ; et ce n'est pas qu'un résultat probabiliste dépendant de tel ou tel comportement de l'hydre : c'est un résultat certain (ce qui est plus fort que de probabilité 1).

Je l'ai évoqué précédemment, ce résultat est lié à des grands ordinaux (pour cette hydre précise, c'est l'ordinal de Bachmann-Howard, dont j'ai déjà parlé). Je reviendrai sur l'aspect mathématique dans une entrée ultérieure : pour l'instant je laisse juste ça sous forme de petit jeu. Et je salue au passage les quelques navigateurs qui implémentent correctement l'affichage du SVG sous contrôle du DOM en JavaScript, parce que ça ne doit pas être ultra facile et ça rend ce genre de petites pages animées possible (et même agréable à écrire : en fait, JavaScript est un langage assez plaisant).

Commentaires

2008-03-23 (dimanche)

Un peu plus d'IPv6

En prévision de la fin d'Internet version 4[#], annoncée pour dans un peu moins de trois ans, et puisque les Dédibox proposent enfin une connectivité IPv6, j'ai enfin décidé de publier les adresses v6 du serveur (qui marchaient depuis un moment, mais qui n'étaient pas employées). Histoire de voir, entre autre, si les gens les contactent : d'ailleurs, depuis hier soir, il y a huit heureux gagnants qui ont gagné un point geek++ pour être venus ici en transports modernes : deux personnes avec des adresses 6to4 en 2002:xyzt:uvws::xyzt:uvws dont un par un smartphone, et six freenautes[#2] (un avec une adresse en 2a01:5d8::/32 qui est l'ancien système de numérotation de Free et les autres en 2a01:e30::/28 qui est leur nouveau système de numérotation).

C'est un peu stupide de dire si vous n'arrivez pas à lire ces lignes, faites-moi signe, mais je vais quand même le dire… Donc, si vous constatez un problème particulier qui serait apparu depuis hier soir, dites-le moi.

[#] Précisons pour ceux qui ne sont pas au courant : la version du protocole Internet que presque tout le monde utilise presque tout le temps (par exemple, c'est très probablement votre cas quand vous consultez Google ou Wikipedia) est la version 4 (nonobstant son nom, on pourrait dire que c'est la première), et elle ne prévoit que quatre milliards d'adresses IP possibles. Il n'y a pas encore quatre milliards d'ordinateurs connectés à Internet, mais on perd forcément pas mal d'espace dans la façon dont on alloue ces adresses (car il faut attribuer des blocs entiers à des fournisseurs d'accès, on ne va pas le faire IP par IP), si bien qu'on arrive maintenant à court. Autour de fin 2010 ou début 2011, l'autorité suprême qui alloue les adresses (l'IANA) n'en aura plus à déléguer, et à peine un an plus tard les différents groupements régionaux de fournisseurs d'accès n'en auront plus non plus. La version 6 du protocole (il n'y a pas vraiment eu de version 5), qui prévoit différentes améliorations dont beaucoup plus d'adresses (on dit parfois spectaculairement qu'il y en a 340282366920938463463374607431768211456 au lieu de 4294967296, mais ce nombre n'a pas beaucoup de sens vu que ce sont des bits qu'on attribue plutôt que des adresses), a été définie il y a une douzaine d'années et est — très lentement — en cours d'adoption. Tous les différents systèmes d'exploitation modernes sont maintenant compatibles IPv6, ainsi que beaucoup de logiciels ; les fournisseurs d'accès commencent timidement à s'y mettre, les sites Web expérimentent, mais il reste encore beaucoup de chemin à faire (mon pipotron me souffle qu'il ne doit même pas y avoir 0.001% du Web qui soit accessible en IPv6).
Pour savoir simplement si vous avez une connectivité IPv6, essayez de vous connecter à IPv6.org et on vous dira soit you are using IPv6 soit you are using IPv4 selon le cas ; vous pouvez aussi aller sur la page du projet Kame et voir si la tortue est animée (auquel cas vous utilisez IPv6) ; ou encore, essayer de vous connecter à ipv6.google.com.

[#2] Ce chiffre ne me surprend pas : je pense que Free a fait énormément de bien à l'utilisation d'IPv6 en l'activant sur ses réseaux.

Commentaires

2008-03-18 (lundi)

Remarques sur le mode de scrutin

Il n'est pas fréquent que je dise du bien d'un mode de scrutin qui est utilisé dans la vie réelle, mais celui qui sert à élire les conseillers municipaux (donc, indirectement, les maires) me semble globalement bon : il s'agit d'un scrutin à la proportionnelle, avec prime à la majorité pour garantir que la stabilité de l'exécutif municipal. Je trouve que cette prime à la majorité (50%, surtout que c'est arrondi à l'entier supérieur) est un peu excessive, cependant : une prime de 25% comme c'est le cas pour les régionales suffirait à assurer une majorité des sièges dès que la liste arrivée en tête a au moins 33% des voix, ce qui doit être à peu près tout le temps le cas (il faudrait une quadrangulaire bien serrée pour faire moins) ; peut-être qu'une prime de 33% serait un compromis. Quoi qu'il en soit, le principe est que la liste ayant obtenu le plus de voix se voit attribuer d'emblée un certain nombre de sièges et que les autres sont répartis à la proportionnelle (entre toutes les listes, y compris celle qui a déjà eu la prime en question). En détails :

On procède à un premier tour de scrutin. Si aucune liste n'obtient la majorité absolue à ce premier tour (c'est-à-dire strictement plus que la moitié des suffrages exprimés), on procède à un second tour de scrutin : pour maintenir sa liste au second tour, il faut avoir recueilli au moins 10% des suffrages exprimés ; les listes ayant obtenu moins de 10% mais au moins 5% des suffrages exprimés peuvent fusionner avec une autre liste (cette fusion est libre, et si elle a lieu l'ordre des candidats peut changer ; en revanche, il n'est pas permis que certains candidats d'une liste du premier tour fusionnent avec une certaine liste et d'autres avec une autre).

Une fois le ou les tours de scrutins effectués, on attribue la moitié des sièges à la liste ayant obtenu le plus de voix : la moitié est arrondue à l'entier supérieur s'il y a au moins cinq sièges à pourvoir, à l'entier inférieur s'il y en a trois ou moins. Pour attribuer le reste des sièges, on écarte les listes qui ont obtenu moins de 5% des voix et on attribue entre toutes les autres listes (y compris celle qui a eu la prime à la majorité) les sièges à la proportionnelle avec la méthode de la plus forte moyenne.

La méthode de la plus forte moyenne (de d'Hondt) signifie qu'on donne d'emblée à chaque liste un nombre de sièges proportionnel à son nombre de voix, arrondi à l'entier inférieur, puis on attribue chaque siège restant à pourvoir selon la règle « bayesienne » suivante : on divise le nombre de voix de chaque liste par un de plus que le nombre de sièges qu'elle a déjà obtenus (de ceux qui sont attribués à la proportionnelle, évidemment !), et la liste qui a le plus grand quotient obtient le siège (ce qui signifie que pour le siège suivant son quotient sera plus petit, évidemment).

Les sièges sont attribués dans l'ordre des listes (donc le premier de la liste aura un siège dès que la liste en reçoit un, le second sera servi en deuxième, etc., et — puisque les listes sont de même longueur que le nombre de sièges à pourvoir — le dernier n'aura de siège que si la liste obtient tous les sièges).

Le maire est ensuite élu par le conseil municipal en son sein.

S'agissant de Paris, Lyon et Marseille, les choses sont plus compliquées car les élections sont sectorisées : les listes sont déposées dans un secteur (qui correspond à un arrondissement dans le cas de Paris et Lyon, à deux arrondissements dans le cas de Marseille), et elles servent à la fois à élire les conseillers municipaux (appelés conseillers de Paris dans le cas de Paris) et les conseillers d'arrondissement du secteur. Chaque liste comporte un nombre de noms égal au nombre de conseillers municipaux plus d'arrondissement attribués au secteur (les conseillers municipaux élus dans le secteur siègent au conseil d'arrondissement, mais on ne les appelle pas conseillers d'arrondissement : le Club Contexte vous remercie de votre attention !). On répartit de la même façon (à la proportionnelle avec prime à la majorité comme expliqué ci-dessus) les conseillers municipaux pour le secteur et les conseillers d'arrondissement[#] : les premiers candidats des listes deviennent conseillers municipaux et les suivants deviennent conseillers d'arrondissement.

Le conseil municipal élit en son sein le maire de la ville, les conseils d'arrondissement élisent les maires d'arrondissement parmi les conseillers municipaux pour le secteur.

Quels que soient les détails mineurs, je trouve que c'est un bon système, et je serais très favorable à ce que l'Assemblée nationale soit élue selon le même mécanisme : disons, un scrutin à la proportionnelle avec prime à la majorité dans chaque région, et on regroupe tout ça en une seule assemblée : ça combinerait les mérites du scrutin à la proportionnelle pure (permettre aux petits partis d'être un peu représentés, éviter que les députés cultivent trop « leur » circonscription au détriment de la représentation nationale) avec certains de ceux du scrutin majoritaire par circonscription[#2] (avoir un minimum d'assise territoriale, et favoriser la formation des majorités stables). Le collège électoral qui élit le président des États-Unis serait aussi bien moins absurde s'il était formé selon ce principe (avoir un semblant de proportionnelle dans chaque état au lieu d'attribuer tous les grands électeurs à l'unique candidat arrivé en tête pour l'État[#3]).

Il y a cependant un point sur lequel on pourrait nettement améliorer le système proportionnel tel qu'il est utilisé en France, c'est qu'au lieu d'élire bêtement les conseillers dans l'ordre des listes, on pourrait utiliser un des divers systèmes qui permettent d'améliorer les choses par rapport à ça — c'est-à-dire d'éviter que l'ordre d'élection soit fixé par la hiérarchie d'un parti mais de donner aux électeurs un poids là-dedans. Le système du vote unique transférable a l'air d'avoir des vertus intéressantes, mais il est sans doute difficile à appliquer en pratique, et je ne suis pas sûr de voir quel système proportionnel il devient si on fixe des listes toutes disjointes (ni s'il y a un système de ce genre qui donne exactement le système proportionnel par la méthode des plus fortes moyennes si on l'applique à des listes fixées).

[#] Une question un peu byzantine est de savoir si on attribue les sièges séparément pour les conseillers municipaux et les conseillers uniquement d'arrondissement ou bien ensemble pour le conseil d'arrondissement (composé des deux). Cela peut faire une différence pour des raisons d'arrondi. Et il se trouve que la différence a effectivement lieu dans le 2^e arrondissement de Paris : les 3 conseillers de Paris pour l'arrondissement sont acquis à la liste d'union de la gauche qui a obtenu 68.34% des suffrages obtenus, et selon qu'on procède ensuite à l'élection des 10 conseillers d'arrondissement au sens strict ou bien qu'on considère que ces 3 conseillers font déjà partie d'une élection de 13=3+10 personnes en bloc, cela donne à l'unique liste adverse soit 1 seul conseiller d'arrondissement (attribué à la proportionnelle sur les 5←10 sièges qui le sont) soit 2 (attribués à la proportionnelle sur les 6←13 sièges qui le sont). D'après les chiffres du ministère de l'intérieur, c'est la première solution qui est la bonne puisqu'ils ne donnent qu'un conseiller d'arrondissement à la liste Lekieffre : i.e., on élit successivement, et avec les mêmes proportions, les conseillers de Paris pour l'arrondissement et les conseillers d'arrondissement au sens strict. J'aimerais bien savoir qui a dû se gratter la tête pour décider pour décider quelle était l'interprétation correcte de la phrase absolument sibylline du Code électoral ! J'aimerais aussi savoir si c'était expressément voulu ou si personne ne s'est posé la question ; en tout cas, ce n'était certainement pas le bon choix : le mode d'élection proportionnel à la plus forte moyenne a des propriétés mathématiques intéressantes et sympathiques (pas de paradoxe de l'Alabama) notamment si, justement, on considère une élection comme emboîtée dans une autre (par exemple, on pourrait élire à la proprotionnelle, simultanément, le présidium d'une assemblée et le reste de l'assemblée, en commençant par pourvoir les sièges du présidium : ce serait une erreur de procéder à deux scrutins séparés, il faudrait continuer à pourvoir les sièges avec les moyennes déjà calculées — et l'élection simultanée du conseil de Paris et des conseils d'arrondissement sont le cas d'école d'application de ces propriétés). Mais bon, il faut reconnaître que ça fait peu souvent une différence.

[#2] On pourrait aussi à cet égard parler du système allemand (Sie haben zwei Stimmen) ; mais les petits malicieux pourraient faire remarquer que celui-ci combine les inconvénients du système proportionnel (les répartitions des sièges sont, in fine, proportionnelles, donc il peut très bien ne pas y avoir de majorité — d'ailleurs…) et du système majoritaire par circonscription (puisque les élus du Bundestag qui ont mandat direct dépendent bien de leur circonscription). Le système allemand avec une prime à la majorité serait peut-être un système raisonnable ; mais en fait, la stabilité ministérielle allemande a surtout l'air de venir du fait que les motions de censure doivent être constructives (i.e., rassembler les voix autour d'un nouveau nom de chancelier).

[#3] Les États-Unis sont particulièrement peu friands de scrutins de listes et, par conséquent, de représentation proportionnelle. Pourtant, il y a un domaine où ils ont effectivement une représentation proportionnelle : c'est entre les États à la Chambre des Représentants (pour fixer le nombre de sièges de chaque État à partir des chiffres du recensement). Avec un système différent de celui qui est employé en France, cependant, qui, pour dire les choses grossièrement, privilégie plutôt l'absence de distorsions entre les États que la qualité de la représentation d'ensemble.

Commentaires

2008-03-16 (dimanche)

J'apprends à compter jusqu'à ψ(ε_Ω+1) et à dompter les hydres

Si j'ai été silencieux pendant deux semaines c'est qu'aussitôt abandonné le nim épicé j'ai été saisi d'une autre obnubilation intellectuelle (et qui me revient périodiquement[#]), c'est celle des ordinaux dénombrables : j'avais déjà écrit des articles de vulgarisation à ce sujet (celui-ci il y a très longtemps et celui-ci il y a un peu moins longtemps, le premier ayant même été traduit en chinois[#2] ; et j'ai beaucoup contribué à l'article de Wikipédia en anglais), cette fois je me suis intéressé aux notations ordinales — c'est-à-dire, en gros, la façon de donner un nom aux (plus petits des) ordinaux dénombrables, en essayant d'aller le plus loin possible, tout en sachant très bien qu'on ne pourra pas atteindre tous les ordinaux dénombrables (ni même tous les ordinaux récursifs). Et j'ai produit les jolis dessins que voici[#3] et surtout ce texte explicatif dont je vais dire un peu plus.

Quand on entend parler des ordinaux pour la première fois, on entend parler de ω, de ω^ω, de ω^ωω, et souvent de la limite de tout ça, qui est ε₀ (qui le plus petit ordinal vérifiant ω^ξ = ξ, c'est-à-dire le plus petit point fixe de ξ↦ω^ξ). Manipuler les ordinaux jusqu'à ε₀ (pour les ajouter, les multiplier ou les exponentier) est facile si on travaille en forme normale de Cantor (c'est-à-dire, informellement, en base ω) itérée pour les exposants ; à partir de ε₀ ça devient un chouïa plus compliqué parce qu'il y a des égalités qui ne sautent pas immédiatement aux yeux (comme le fait que ω^ε₀+1 = ε₀·ω), mais on finit par s'y habituer. Le problème est plutôt de monter aussi loin que possible : si ε₁ est la prochaine solution de ω^ξ = ξ, et ainsi de suite, jusqu'où ira-t-on ? On pourrait appeller ζ₀ la limite de la suite ε₀, ε_ε0, ε_εε0, c'est-à-dire le premier point fixe de ξ↦ε_ξ, on peut continuer à jouer ainsi avec les lettres grecques qui énumèrent les points fixes les unes des autres, si bien qu'on finit par avoir besoin d'un alphabet grec transfini : c'est ce qu'on appelle le schéma φ de Veblen (à deux variables, pour commencer), chaque rang énumérant les points fixes du rang précédent. Seulement, on arrive à court de ce schéma aussi lorsqu'on tombe sur la première lettre grecque qui est, pour ainsi dire, son propre rang dans l'alphabet. C'est cet ordinal (toujours dénombrable, bien sûr) qu'on appelle l'ordinal de Feferman-Schütte (et c'est la limite des ordinaux pour lesquels le schéma de Veblen à deux variables fournit des notations).

Car certains grands ordinaux dénombrables, comme ça, ont des noms de gens associés : l'ordinal de Feferman-Schütte, l'ordinal d'Ackermann, les petit et grand ordinaux de Veblen, l'ordinal de Bachmann-Howard, l'ordinal de Takeuti-Feferman-Buchholz (c'est moi qui l'appelle comme ça) et peut-être plus encore. En gros, il y a deux approches possibles pour donner des noms systématiques à de grands ordinaux dénombrables :

• L'approche prédicative part, pour ainsi dire, de bas en haut. Elle consiste à appliquer des fonctions toujours plus compliquées définies comme des points fixes de points fixes de points fixes de, etc., c'est-à-dire des constructions comme le schéma de Veblen. En utilisant cette approche on peut certainement définir l'ordinal de Feferman-Schütte (parfois considéré comme la limite des ordinaux prédicatifs, mais à mon avis c'est une bêtise) avec le schéma de Veblen à deux indices ; et, en travaillant un peu plus, aussi le petit — voire le grand — ordinal de Veblen (avec des schémas de Veblen à plus de variables). Atteindre l'ordinal de Bachmann-Howard de cette façon semble à peu près impossible (peut-être pas de façon théorique mais certainement en pratique), pour ne rien dire des encore plus grands.
• L'approche imprédicative par écrasement est plus inattendue, plus difficile à comprendre, mais beaucoup plus puissante, et permet sans trop de difficulté d'atteindre l'ordinal de Bachmann-Howard et, en travaillant un peu plus, des ordinaux encore plus grands. L'idée surprenante est que pour construire des notations pour de grands ordinaux dénombrables on va en construire pour certains ordinaux indénombrables et utiliser une fonction écrasante qui les renvoie sur des ordinaux dénombrables. Intuitivement, l'idée est quelque chose du style : si on tombe à court de notations pour les ordinaux dénombrables, faisons un saut jusqu'aux indénombrables qui nous fournissent forcément des choses plus grandes — et rendons-nous ensuite compte que si on met les notations en question dans l'ordre, ça ne fait évidemment qu'un ordinal dénombrable. (C'est ainsi que l'ordinal de Bachmann-Howard se note quelque chose comme le ψ(ε_Ω+1) du titre de cette entrée : ici, ε_Ω+1 est un ordinal qui n'est pas dénombrable, mais ψ(ε_Ω+1) l'est.)

Les jolis petits dessins mentionnés ci-dessus représentent les ordinaux (enfin, un petit échantillon d'ordinaux !) jusqu'au petit ordinal de Veblen, c'est-à-dire à peu près l'étendue de l'approche prédicative, en leur donnant si possible deux noms, l'un utilisant l'approche prédicative (avec les fonctions φ de Veblen) et l'autre utilisant une fonction écrasante ψ. Pour les arbres, je vais en dire plus dans une minute. Concernant la fonction écrasante, j'ai écrit ce texte explicatif : reste à savoir où l'insérer dans Wikipédia (si possible sans qu'on m'accuse de faire de la original research). Peut-être que ce n'était pas la meilleure place pour ça, en fait. Mais quelles que soient ses vertus pédagogiques (ou pas), il m'aura au moins permis de bien comprendre ces choses-là, et donc, en quelque sorte, d'apprendre à « compter » jusqu'à l'ordinal de Bachmann-Howard (sans doute même au-delà).

Ce qui est étrange, c'est qu'on a parfois l'impression que les ordinaux (dénombrables, au moins, car les autres sont juste inimaginables) sont « tous pareils » : quand j'essaie d'expliquer comment on grimpe jusqu'à tel ou tel ordinal, on se retrouve souvent à prononcer des phrases comme et on recommence tout ce truc, et ainsi de suite jusqu'à, etc. Pourtant, au contraire, il n'y a pas de structure mathématique plus rigide[#4] que les ordinaux.

L'autre chose étrange, c'est que les ordinaux apparaissent très peu dans les mathématiques standards, hors théorie des ensembles (au point que la plupart des mathématiciens considèrent que c'est un peu un gros mot). Pourtant, on pourrait dire qu'à chaque fois qu'il y a un processus dont la terminaison est garantie en temps fini (et c'est chose fort courante en mathématiques ou en informatique), il y a un ordinal qui se cache[#5]. Seulement, en pratique, cet ordinal n'est jamais bien grand (très souvent c'est simplement un entier naturel, en fait, quand il y a une borne universelle sur la longueur du processus, ou bien ω quand il y a une borne qui dépend d'un unique premier choix), donc les mathématiciens n'ont pas trop besoin de savoir compter loin.

Parmi les processus qui terminent forcément et auxquels sont associés des ordinaux pas trop petits, il y en a qui sont souvent donnés en exemple parce qu'ils sont récréatifs et faciles à comprendre : ce sont les jeux de l'hydre. En gros il s'agit de partir d'une structure finie, typiquement un arbre, censé symboliser l'hydre. Un joueur, censé symboliser Hercule, réduit la structure par petites étapes (du genre, couper une branche de l'arbre, parfois avec des contraintes sur la branche) : mais dès qu'on la réduit, la structure grandit de façon apparemment démesurée (l'hydre repousse des nouvelles têtes), selon des règles plus ou moins compliquées. Selon toute apparence, Hercule n'a aucune chance de gagner, et le nombre de têtes de l'hydre croît de façon vertigineuse ; en réalité, les règles sont faites en sorte qu'à chaque configuration de l'hydre est associé un ordinal et que cet ordinal décroît forcément, de sorte que le jeu termine toujours en temps fini. Le cas le plus classique est l'hydre de Kirby-Paris, dont il y a par exemple une description ici (avec même une petite applet pour jouer) : dans ce cas, l'ordinal est ε₀ (au sens où chaque arbre fini encode un ordinal inférieur à ε₀ de façon à décroître à chaque coup d'Hercule, ce qui garantit la terminaison, et les ordinaux). Mais il y a d'autres variantes (parfois compliquées) du jeu de l'hydre, qui doivent être associées à d'autres ordinaux éventuellement plus grands : par exemple, l'hydre de Kirby-Paris ne croît jamais en hauteur, seulement en largeur, mais on doit pouvoir en faire une qui croît en hauteur aussi. J'aimerais définir une hydre de Veblen mais je n'ai pas trouvé de description simple ou qui me satisfaisse.

L'ordre sur les arbres finis enracinés (et à descendants ordonnés) qui leur donne la taille du petit ordinal de Veblen est défini récursivement comme suit :

Un arbre (fini enraciné) A est strictement inférieur à B lorsque soit il existe une branche (i.e., un sous-arbre immédiat, i.e., un fils) B′ de B qui soit supérieur ou égal à A, soit les deux conditions suivantes sont vérifiées : d'une part toute branche A′ de A est strictement inférieur à B et, d'autre part la liste des branches de A est lexicographiquement strictement inférieure à celle des branches de B (en donnant le plus de poids aux branches les plus à gauche et en convenant que s'il y a moins de branches dans A alors la liste est lexicographiquement inférieure).

— c'est un peu long à dire, mais ce n'est pas vraiment compliqué[#6]. En gros ça dit qu'on compare les branches lexicographiquement mais avec l'exception évidemment nécessaire que l'arbre tout entier doit être supérieur à chacune de ses branches. Ce qui n'est pas totalement évident, c'est que c'est bien un bon ordre (et que la relation d'égalité associée est bien l'égalité à laquelle on s'attend sur les arbres finis enracinés !), et la longueur de ce bon ordre est précisément le petit ordinal de Veblen. Donc à tout arbre fini enraciné est associé, de cette façon, un ordinal inférieur au petit ordinal de Veblen et c'est ça que j'ai représenté dans mes pages de petits dessins. Et il doit y avoir un jeu d'hydre associé à cet ordre, mais je n'arrive pas à décrire de façon générale quelle en serait la règle[#7].

[#] En l'occurrence, c'est quand même parti du jeu de nim, puisqu'il y a un problème — à ma connaissance encore ouvert — posé par Conway en 1976 qui est de déterminer le deuxième ordinal qui soit un transcendant pour la multiplication de nim (sachant que le premier est ω^ωω).

[#2] Il va de soi que tous les liens que je donnais en 2005 sont cassés. <soupir> La traduction chinoise en question, parue dans 三思科学, existe cependant encore, elle est trouvable par son titre, 不同寻常的数.

[#3] Produits par ce programme Perl et qui font ensuite beaucoup souffrir TeX (j'ai dû augmenter la mémoire qu'il peut prendre, et ça compile en plus de 20s sur ma machine qui n'est pourtant pas minable). J'espère ne décevoir personne en avouant que les noms n'ont pas été générés automatiquement…

[#4] Par rigide, j'entends, techniquement, qu'ils n'ont pas d'automorphismes : lorsque deux ensembles bien ordonnés sont isomorphes, l'isomorphisme est unique — c'est-à-dire, avec les mains, qu'il n'y a qu'une seule façon de les faire se correspondre. Donc si on peut se poser la question philosophique complètement oiseuse de savoir si le ℂ auquel je pense est bien le même que celui de mon voisin (a-t-on l'un et l'autre le même i ? ou sont-ils conjugués complexes ?), cette question ne peut pas se poser pour les ordinaux.

[#5] On pourrait le caractériser ainsi : soit P un processus dont un théorème nous assure qu'il termine toujours, quels que soient certains choix effectués ; on considère un jeu à deux joueurs où un joueur applique le processus P, à raison d'une étape à chaque tour, en effectuant les choix qu'il veut, et l'autre joueur part d'un certain ordinal α et peut à chaque étape le décroître comme il lui plaît. Le premier joueur qui termine a perdu (c'est-à-dire le joueur-processus si le processus termine, et le joueur-ordinal si l'ordinal tombe à zéro) : à partir d'un certain ordinal, c'est le joueur-ordinal qui a une stratégie gagnante — et cet ordinal mesure la longueur de terminaison du processus P.

[#6] Pour comparaison, l'ordre sur les arbres finis enracinés (sans distinction des descendants) qui conduit à l'hydre de Kirby-Paris est le suivant : un arbre A est inférieur à un arbre B lorsque, en triant les branches de A et celles de B pour l'ordre en question et en regardant le nombre d'occurrence de chacune, le nombre pour A est lexicographiquement inférieur au nombre pour B en donnant au nombre des branches les plus grandes le plus de poids. Cette fois-ci l'ordinal est ε₀ (beaucoup plus petit, donc), et, pour ainsi dire, les arbres grandissent en largeur avant de grandir en profondeur (pour l'ordre de Veblen, c'est le contraire).

[#7] Ça devrait ressembler à ceci : quand on coupe une tête, toutes les têtes situées à sa droite s'énervent, et ça leur fait pousser sur chacune une copie du sous-arbre complet qui les relie au chemin de coupe (têtes énervées comprises) et on recommence ça aussi souvent que l'hydre le veut. Malheureusement, sous cette forme, ça ne marche pas.

Commentaires

2008-03-02 (dimanche)

Le jeu de nim épicé

Je disais récemment que les idées scientifiques ont tendance à ressembler aux tamagotchis : on commence à les élever et rapidement elles vous accaparent l'esprit en demandant sans arrêt votre attention.

Je réfléchissais à la théorie combinatoire[#] des jeux quand je suis tombé sur l'idée du jeu suivant (qui a certainement déjà été décrit et étudié, mais il est difficile de trouver sous quel nom), que j'appellerai le jeu de nim épicé.

Tout d'abord je rappelle ce qu'est le jeu de nim usuel : il s'agit d'un jeu (impartial, à connaissance complète, à deux joueurs) extrêmement simple, dans lequel l'état du jeu est donné par un certain nombre de lignes de bâtonnets (ou quelconques autres jetons : tas de pièces, rangées d'alumettes, ce que vous voudrez ; il en existe aussi des avatars un petit peu moins évidents où, par exemple, on avance des pions sur un échiquier sans avoir le droit de les reculer). Seul compte le nombre de bâtonnets présent sur chaque ligne (il n'y a pas d'ordre, pas de structure supplémentaire). La règle du jeu est simplissime : les joueurs jouent tour à tour et chacun, quand c'est son tour, peut et doit retirer des bâtonnets situés sur une ligne — il doit en retirer au moins un et peut en retirer autant qu'il veut, y compris vider (et donc supprimer) la ligne, mais il ne peut en un tour retirer des bâtonnets que d'une seule ligne (de son choix). Normalement, le joueur qui ne peut plus jouer a perdu (i.e., celui qui retire le dernier bâtonnet a gagné, puisque son adversaire est dans l'impossibilité de jouer) : en fait, la version misère, où celui qui retire le dernier bâtonnet perd, est peut-être plus commune pour le jeu de nim, mais elle est en fait très semblable[#2] et moins intéressante mathématiquement.

Dans n'importe quel jeu de ce genre (i.e., un jeu impartial, à connaissance complète, à deux joueurs, et qui termine toujours en temps fini sur le gain d'un des joueurs avec par convention perte du joueur qui ne peut plus jouer), l'un des deux joueurs a forcément une stratégie gagnante. En fait, on peut définir deux sortes de positions du jeu : les positions dites nulles[#3] — qui sont celles à partir desquelles le second joueur a une stratégie gagnante —, et les autres (généralement les plus nombreuses). La définition (récursive !) est qu'une position nulle est une position qui ne conduit qu'à des positions non nulles (y compris si elle ne conduit à rien du tout, car alors le joueur qui vient de jouer à gagné) et, a contrario, une position non nulle est une position qui conduit à au moins une position nulle. La stratégie gagnante consiste à jouer, autant que c'est possible, pour mettre le jeu dans une position nulle (auquel cas le joueur adverse sera obligé de jouer pour aller dans une position non nulle, donc on sera assuré de pouvoir jouer vers une position nulle, et ainsi de suite : comme on peut toujours gagner, on ne peut pas perdre). Connaître la stratégie gagnante revient donc à identifier les positions nulles (pour pouvoir jouer vers elles).

Dans le cas du jeu de nim, elles ont une description mathématiquement simple : sont nulles les positions telles que le « ou exclusif » du nombre de bâtonnets de chaque ligne (écrits en binaire) soit nul. Par exemple, la position de départ habituelle, (1,3,5,7) (ce qui signifie : un bâtonnet sur une ligne, trois sur une autre, cinq sur une troisième, et sept sur la dernière ligne) est nulle car 001⊕011⊕101⊕111=000 : cela signifie qu'au jeu de nim usuel, à partir de cette position, le joueur qui ne commence pas peut gagner le jeu à coup sûr (par exemple, si le premier joueur retire deux bâtonnets de la dernière ligne, c'est-à-dire joue vers (1,3,5,5), position non nulle, on répondra vers (1,1,5,5), position nulle, et il est d'ailleurs clair qu'on a alors une stratégie gagnante en reproduisant les coups d'une paire de lignes (1,5) sur l'autre).

J'en viens donc au jeu de nim épicé : la différence avec le jeu nim normal est qu'il existe deux sortes de lignes, des lignes épicées et des lignes normales (ou fades). La règle du jeu est la même (on peut retirer autant de bâtonnets qu'on veut, mais d'une ligne seulement) avec la seule différence que lorsqu'un joueur retire des bâtonnets d'une ligne épicée, son adversaire ne peut pas en faire autant au coup immédiatement après (il doit retirer des bâtonnets d'une ligne fade — et s'il n'en reste aucun, il a perdu). Autrement dit, on ne peut consommer deux coups de suite des bâtonnets épicés. Une position du jeu est déterminée par le nombre de bâtonnets dans les lignes de chaque sorte (je les écrirai en commençant par les lignes fades) et par le fait que le coup immédiatement précédet ait été épicé ou non.

Exemple : en commençant sur (1,2,11;4;4), c'est-à-dire qu'il y a trois lignes fades avec 1, 2 et 11 bâtonnets, et deux lignes épicées avec 4 bâtonnets chacune, le premier joueur pourrait jouer vers (1,2,5;4;4), le second joueur répliquerait avec (1,2,5;4,2)^H (le H, comme hot signifiant qu'on vient de jouer épicé, donc que le coup suivant sera forcément fade), le premier joueur tenterait maladroitement (1,2,3;4,2), ce à quoi on rétorquera (1,2,3;2,2)^H, et une tentative désespérée vers (1,2,1;2,2) provoquera inévitablement la réplique (1,2,1;2)^H, et il n'y a plus de doute sur qui a gagné.

La question à cent zorkmids est donc : quelles sont les positions nulles du jeu de nim épicé ? Peut-on les décrire de façon synthétique comme pour le jeu de nim usuel ?

Je n'ai que des réponses partielles à cette question. Je peux facilement faire produire à mon ordinateur des tables gigantesques de positions nulles, mais ensuite trouver la logique ressemble à un test d'intelligence. Et si c'est un test d'intelligence, j'ai échoué : j'ai trouvé beaucoup de motifs partiels, mais aucune decription complète.

Il est clair que si le nombre total de bâtonnets épicés est strictement supérieur au nombre total de bâtonnets fades (et que la position n'est pas chaude, i.e., qu'on peut jouer épicé), alors la position est non nulle : en effet, le premier joueur a la stratégie gagnante consistant à manger les épices, c'est-à-dire retirer un quelconque bâtonnet épicé, auquel cas son adversaire devra en retirer un fade, puis le premier joueur retire de nouveau un épicé, et ainsi de suite jusqu'à épuisement des fades auquel moment le second joueur perd. Dans « beaucoup » de cas, une position nulle s'obtient en complétant une telle position jusqu'à ce que le nombre total de bâtonnets fades égale le nombre total d'épicés : notamment, s'il y a une seule ligne fade, il est facile de voir que la condition de nullité est précisément que le nombre de bâtonnets de cette ligne soit égal au nombre total de bâtonnets épicés ; il en va de même si les épicés sont dans des lignes d'un seul bâtonnet chacune (i.e., de nouveau, quelle que soit la répartition des fades, la condition de nullité sera que les fades soient aussi nombreux que les épicés). Mais parfois, il faut plus de fades : par exemple, s'il y a exactement deux lignes de fades dont une avec un seul bâtonnet, la condition de nullité est que le nombre total de fades soit deux de plus que le nombre total d'épicés si toutes les lignes épicées ont un nombre pair de bâtonnets (alors que c'est égalité s'il y a une ligne épicée avec un nombre impair de bâtonnets) — je sais le démontrer, mais je ne sais pas le généraliser correctement. Je ne sais pas « expliquer » de façon satisfaisante le fait que (2,9;6,4) ou (3,8;6,4) ou (1,2,8;6,4) (et pas (2,8;6,4) ou (2,n;6,4) pour un quelconque autre n) soient des positions nulles. C'est mystérieux : je cherche encore le motif, mais je commence à douter de son existence…

Évidemment, le jeu de nim se prête à quantité d'autres variations (on pourrait interdire de reprendre des bâtonnets de la ligne qui vient d'être diminuée, ou bien seulement pour certaines lignes, ou avoir plusieurs sortes d'épices, que sais-je encore…). Mais celle-ci m'est venue à l'esprit dans le cours d'une réflexion plus générale, alors maintenant elle m'obsède.

[#] Le terme combinatoire est là pour insister sur le fait qu'il ne s'agit pas de la théorie des jeux dans le sens où on l'entend d'habitude (jeux à la von Neumann, équilibres de Nash, tout ça) mais de jeux à information complète. Pour la bible sur le sujet, voir le très exotique Winning Ways de Berlekamp, Conway et Guy. On peut dire que c'est Conway qui a inventé la théorie combinatoire des jeux partiaux, la théorie combinatoire des jeux impartiaux — théorie de Sprague-Grundy, par exemple — est plus ancienne.

[#2] Pour jouer à la version misère, si on connaît la stratégie optimale de la version normale du nim décrite plus loin, il suffit de jouer comme pour la version normale sauf lorsqu'on ne va laisser que des lignes avec (zéro ou) un bâtonnet : à ce moment-là on en laisse un de moins (ou un de plus).

[#3] Le choix du mot nul, pour les jeux où le second joueur a une stratégie gagnante, pourra sembler bizarre. L'explication est que si on fait la somme d'un tel jeu et d'un jeu G quelconque — la somme étant à comprendre au sens où chaque joueur peut jouer dans une composante quelconque de la somme — alors la somme en question a la même caractéristique que le jeu G. Ou encore, les positions nulles sont celles dont la fonction de Grundy est nulle.

Commentaires