Conway, Fractran et autres broutilles

(dans la série François gazouille)

John Conway nous fait surtout penser au modèle d'automates cellulaires qui porte son nom, que Scientific American a popularisé sous le nom Life (le jeu de la vie), il y a peut-être une trentaine d'années déjà. La plupart d'entre vous connaissez assez bien ce jeu. Il avait provoqué un engouement universel dans les Universités, à l'époque. Les ordinateurs étaient encore difficiles d'accès, et fort peu interactifs, plusieurs ont passé de longues soirées à barbouiller des générations de cellules, d'une feuille de papier quadrillé à l'autre, absolument mystifiés d'apercevoir un comportement global complexe, mais issu des influences d'un voisinage restreint et d'actions extrêmement locales.

Voir émerger la complexité d'une simplicité quasi dérisoire, cela étonne toujours. Nous avons plutôt l'habitude du contraire: la désintégration radio-active est bien prévisible prise globalement, la loi de la limite centrale banalise toutes les distributions aléatoires, et certains comportements de foule sont bien plus simples que celui des individus qui la composent. Nous sommes fascinés par les ensembles de Mandelbrot, ou même par ces images que xmartin (fractals itératifs) affiche sur le fond de nos écrans. Au-delà de l'effet visuel et des jolies couleurs, une complexité infinie résulte de l'application de règles absolument simples, pourtant. Les mathématiques transportent en elles de telles étrangetés, qui nous hypnotisent.

J'ai passé de longs moment à observer un autre jeu, peut-être moins connu, mais fort simple. Une grille est complètement peuplée de points noirs ou blancs, au hasard. Chaque point représente un individu, et sa couleur une opinion politique, dans une société où seulement deux opinions existent. L'influence de chaque individu ne va pas plus loin que ses huit voisins immédiats, un à la fois. Un individu fera prendre sa propre couleur à son interlocuteur, ou encore, prendra la sienne, dépendamment lequel des deux est le plus convainquant. En fait, chaque itération choisit une paire de points voisins tout à fait au hasard, et au hasard aussi, l'un des points choisi prendra la couleur de l'autre.

Comme un ordinateur peut exécuter une telle simulation à bonne vitesse, en autant que l'on soigne un peu la programmation, il est passionnant de voir évoluer une telle sociéte. La grisaille du départ est assez rapidement remplacée par des petits pays, qui grossissent et deviennent des continents, dont les frontières se dessinent et s'affermissent avec le temps. Est-ce qu'une opinion finira par complètement l'emporter sur l'autre? Je vous suggère d'en faire l'essai, et de me partager vos trouvailles.

Voici un autre exemple de complexité cachée, que l'on doit encore une fois au John Conway de tout-à-l'heure, dit-on. Un ordinateur reçoit des données, exécute un programme, et produit des résultats. Voici donc une machine hypothétique, qui reçoit une donnée sous la forme d'un nombre entier, placé dans son unique accumulateur. Elle reçoit aussi un programme sous la forme d'une série de fractions. Par exemple: l'accumulateur pourait recevoir la donnée 2, et le programme consisterait dans la suite de fractions: 17/91, 78/85, 19/51, 23/38, 29/33, 77/29, 95/23, 77/19, 1/17, 11/13, 13/11, 15/14, 15/2 et 55/1. Je vous donne les détails, pour que vous puissiez faire fonctionner tout ça sur votre ordinateur préféré.

La machine tente la multiplication l'accumulateur par la première fraction, ou la seconde, et ainsi de suite dans l'ordre, mais n'accepte de le faire uniquement que si le résultat est un nombre exactement entier. Si toutes les fractions sont essayées et qu'aucune ne fournit un résultat entier, alors la machine cesse de fonctionner, elle s'arrête. Dans l'exemple donné plus haut, la dernière fraction possède 1 comme dénominateur, on peut en déduire que la machine ne s'arrêtera jamais pour ce programme-là.

Aussitôt qu'une multiplication réussit en donnant un nombre entier, alors une étape de la machine est complétée, et l'on ne va plus avant dans la liste des fractions. Plutôt, l'accumulateur est examiné pour voir s'il contient un exposant exact de deux (autrement dit, si en binaire, l'accumulateur contient un seul bit à un suivi uniquement de bits à zéro). Dans ce cas uniquement, l'exposant de deux (le nombre de bits zéro après le bit un) est imprimé, et l'on continue. L'étape suivante débute alors immédiatement avec la première fraction de la liste.

Je ne vous ai pas donné au hasard, plus haut, l'accumulateur initial et la suite de fractions. Ce programme exécute un algorithme précis, reconnaissable facilement aux résultats imprimés. Mais je vous laisse le soin de découvrir ce que ce programme calcule exactement. Si nous travaillons bien de la même manière, le premier résultat sera imprimé après 19 étapes, le second résultat apparaîtra après 69 étapes, et le troisième après 280 étapes. Ce seront trois nombres plus petits que 10.

Conway aurait donné le nom Fractran à cette machine, pour rire de FORTRAN probablement, et en faisant un jeu de mot sur fraction. Seriez-vous capables d'imaginer un programme Fractran, c'est-à-dire une série de fractions, capable d'imprimer bêtement la valeur de l'accumulateur au départ? Ou d'imprimer le carré de cette valeur? Ou d'imprimer une valeur constante? Vous avez le droit de coder la donnée de départ spécialement, si cela vous aide.

Un minuscule problème que vous rencontrerez, en implantant une machine Fractran, sera de vérifier si un nombre entier est un exposant exact de deux. Dans le langage C, cela se vérifie par l'énoncé suivant:

  if ((valeur & valeur - 1) == 0)
    printf ("%d est un exposant de deux\n", valeur);
  else
    printf ("%d n'est pas un exposant de deux\n", valeur);


Est-ce que ce test, à l'intérieur du if, ne vous semble pas un peu mystérieux? Comprenez-vous bien sa logique? Si oui, sauriez-vous imaginer un test de même nature qui vérifie si un nombre est exactement la somme de deux exposants de deux? Ou leur différence?

Sur le même air d'aller, en réfléchissant un peu, on voit bien qu'un nombre est un exposant exact de deux (ou la somme de deux exposants de deux), il suffit de compter le nombre de bits à un dans l'accumulateur et vérifier que cette somme vaut un (ou deux). Certains ordinateurs possèdent une instruction unique qui fait le décompte des bits valant un, dans un registre. Mais le langage C n'y donne pas accès. Existerait-il alors, dans le langage C, quelque façon efficace de compter le nombre de bits allumés, dans la représentation binaire d'un entier?

C'est le temps, je crois, de laisser votre curiosité vous amuser un peu. En cherchant des réponses aux petites questions données plus haut, vous trouverez au moins un peu de plaisir!

Avec mon gazou le plus amical!
François Pinard, mars 1996.