Le calcul par le caviar

lundi 11 mai 2015
par  Alain BUSSER

Ce jeu est similaire au jeu de la vie et au jeu des alligators, par les points suivants :

  • Il s’agit d’un jeu de vie artificielle ;
  • C’est un jeu à zéro joueur ;
  • Ce jeu est Turing-complet.

En effet il simule les tague systèmes d’Emil Post, apparus en plusieurs étapes (1921, 1943 et 1947) dans les travaux que celui-ci consacrait au problème du mot.

HTML - 234.3 ko
théorie du jeu
Simulation de tag-systems en ligne, et en CoffeeScript
HTML - 129.5 ko
le jeu en ligne avec animations
c’est en touchant qu’on apprend

historique de la notion

Ces travaux, largement antérieurs à la construction des premiers ordinateurs, viennent de l’algèbre, et plus particulièrement la théorie des groupes [1]

La vie est-elle un système de tague ?

Non [2]

Le jeu parle donc de poissons pondant des œufs : C’est un jœufs ! Au début du jeu, on a une population initiale d’œufs appelée axiome [3]. Ci-dessous ce sont les 6 œufs bleus posés sur le sable en-dessous de l’eau. En effet la moitié supérieure de l’écran est un aquarium dans lequel évoluent les poissons.

Dans le sable, on voit une sorte de poste (!) de pilotage, essentiellement formé d’un tableau. Celui ci-dessus indique que

  • lorsqu’un poisson bleu pond, c’est toujours un œuf rouge suivi d’un œuf vert [4] ;
  • lorsqu’un poisson rouge pond, c’est juste un œuf bleu [5] ;
  • lorsqu’un poisson vert pond, c’est toujours trois œufs bleus [6].

Mais ce n’est pas tout : Lorsqu’un œuf éclot, il donne naissance à un poisson de la même couleur que lui, et celui-ci va pondre ses œufs tout à droite. Et en plus, lorsqu’un œuf éclot, il détruit un certain nombre de ses voisins dans l’explosion [7]. Enfin, un volcan sur la gauche amène juste assez de chaleur pour permettre à l’œuf le plus à gauche d’éclore en premier.

Définir un micromonde se fait donc en modifiant les règles de reproduction, ainsi que la population initiale (ou axiome).


Collatz

En fait, l’exemple ci-dessus simule la suite de Collatz [8]. Voici comment on peut le programmer en Bourne-Again shell :

axiom='bbb'
while [ ${#axiom} -gt 1 ]
do
    eggs=${axiom:0:2}
    case ${eggs:0:1} in
        'b')
            axiom=$axiom'rv';;
        'g')
            axiom=$axiom'b';;
        'v')
            axiom=$axiom'bbb';;
    esac
    axiom=${axiom#$eggs}
    echo $axiom
done

Le symbole « dollar » placé devant le nom d’une variable, donne sa valeur. Mais si après le nom de la chaîne de caractères on met des nombres il y a découpage ; et si on met le symbole « dièse » on obtient la longueur de la chaîne. gt signifie « greater than » et esac clôt les tests case. Enfin la concaténation est notée le plus simplement du monde...


On va voir ci-dessous comment on peut modifier le jeu pour qu’il simule le problème de Post (1921). Tout d’abord on actionne les curseurs pour que

  • Il n’y ait plus que deux couleurs donc plus que deux règles ;
  • Le rayon d’action de l’explosion-éclosion d’un œuf soit 3 et non 2 (l’œuf détruit 2 voisins en éclosant).

On voit que le tableau ne comporte plus que deux lignes, le poisson vert ayant disparu. Maintenant on voudrait que le poisson bleu ponde deux œufs. On peut ajouter des œufs à la règle de production en les faisant glisser du bas de l’écran vers l’entrée du tableau choisie, mais on doit d’abord enlever les œufs rouge et vert, ce qu’on fait en tapant deux fois sur le poisson bleu (chaque « tap » enlève le dernier œuf) :

Ensuite on fait glisser deux fois de suite l’œuf bleu en bas vers la case devenue vide du tableau :

Pour le poisson rouge, la pondaison est plus prolifique et plus multicolore : Deux œufs rouges, un œuf bleu et un troisième œuf rouge. Donc, un tap sur le poisson rouge pour enlever l’œuf bleu, puis on fait glisser successivement l’œuf rouge deux fois, l’œuf bleu et encore l’œuf rouge :

Cet écosystème a une évolution dépendant grandement de l’« axiome » c’est-à-dire de la configuration des œufs bleus et des œufs rouges initiale. Par exemple la population oscille si sa configuration initiale est formée de trois œufs bleus suivis d’un œuf rouge. Pour enlever le dernier œuf de l’axiome, il suffit de le casser en tapant dessus :

Une fois qu’il ne reste plus que 3 œufs bleus, on fait glisser l’œuf rouge du bas (marqué « r ») vers l’axiome pour enrichir celui-ci d’un œuf rouge :

Maintenant on peut jouer. En touchant l’eau (pas l’axiome, au-dessus de celui-ci) on déclenche une éruption volcanique qui fait éclore l’œuf de gauche. Comme celui-ci est bleu il en sort un poisson bleu pendant que l’œuf et ses deux voisins se désagrègent :

Ce poisson va alors, comme il a été programmé pour cela, pondre deux œufs bleus après l’œuf rouge, ce qui ne suffit pas à compenser la perte des trois œufs bleus, et la population est maintenant en danger :

Ensuite, le poisson bleu file vers la droite de l’écran, et quitte cette zone volcanique sous-marine. Si ensuite on tape à nouveau sur l’aquarium, c’est l’œuf rouge qui va éclore puisqu’il est tout à gauche. Il va donc donner naissance à un poisson rouge :

Heureusement d’ailleurs, parce que les trois œufs ayant été détruits dans l’éclosion, il n’y a plus d’œuf. Mais le poisson rouge pond 4 œufs :

Le premier d’entre œufseux est rouge, il en sort donc un poisson rouge :

La population augmente donc à nouveau :

D’autant que le premier œuf étant toujours rouge, il en sort à nouveau un poisson rouge :

On arrive à une population de 6 œufs :

Mais cette fois-ci le poisson qui sort est bleu :

ce qui fait redescendre la population à 5 œufs :

Le poisson suivant est donc rouge :

La population repasse alors à 6 œufs :

Mais le poisson suivant est bleu :

La population obtenue est la même que l’avant-dernière :

La population est donc finalement périodique de période 2, donc ne risque plus de s’éteindre. D’autres populations s’éteignent comme par exemple celles ne comportant que des œufs bleus. Saurez-vous en trouver d’autres ?


version bash

Ici on ne sait pas si la boucle finit alors on boucle 20 fois, pour voir :

axiom='rrbrbr'
for n in `seq 1 20`; do
    egg=${axiom:0:3}
    case ${egg:0:1}
        'b')
            axiom=$axiom'bb';;
        'r')
            axiom=$axiom'rrbr';;
    esac
    axiom=${axiom#$egg}
    echo $axiom
done


Turing

En fait, il résulte d’un théorème de Wang (1963) que les tague systèmes de Post sont Turing-complets (à l’exception des 0-tags ou des 1-tags). Ainsi, on peut simuler un système de tague avec une machine de Turing : Le poisson, dont l’état interne est représenté par sa couleur actuelle, et qui agit sur une bande représentée par le caviar. Dans ce cas le nombre d’états visible est égal au nombre de symboles (les couleurs).

Dans le jeu ci-dessous, il y a 7 couleurs possibles (donc 7 règles de production possibles) :

couleurs symboles
bleu b
rouge r
vert v
magenta m
cyan c
jaune j
noir n

On peut enregistrer ou communiquer un micromonde par des chaînes de caractères, en ouvrant le clavier (en appuyant un nombre impair de fois sur le bouton idoine) et en copiant-collant les chaînes de caractères obtenues (attention : Elles se mettent à jour lors de l’évolution de l’écosystème) .


La version du jeu en ligne ci-dessous utilise le clavier [9] pour entrer ou modifier les règles et l’axiome : toucher le bouton « clavier » puis programmer un micromonde afin de l’explorer :


Calculviar

L'écosystème ci-dessous est basé sur 3 règles de reproduction et chaque éclosion détruit 2 œufs


          Conclusion provisoire

          • Il est possible de transformer ce jeu à 0 joueur en un jeu à un joueur (« réussite » ou « solitaire (patience) »), en donnant une population à atteindre et en demandant au joueur la population initiale permettant d’arriver à cette population « finale ». On peut même en faire un métajeu en demandant également pour quelles règles de production on peut arriver à ce but [10]
          • Pour les enfants les plus tactiles, les œufs peuvent être représentés par des perles de différentes couleurs et on peut jouer sur un collier, par exemple pour le problème de Post ci-dessus, à chaque tour de jeu, on enlève les 3 perles de gauche, on regarde la couleur de la plus senestre d’entre elles, et si elle est bleue on enfile 2 perles bleues à droite, sinon on enfile une rouge, une bleue et deux rouges. Avec des perles de grande taille sur des barres de métal, le PE peut « afficher » les règles au tableau. La version individuelle est assez bon marché avec des perles de plastique comme on en vend pour les petites filles.
          • Les enfants aveugles peuvent jouer aussi si les perles sont de forme ou de taille différente.
          • Le jeu est praticable sitôt que l’enfant distingue les couleurs et sait compter jusqu’à 4, donc a priori assez jeune.
          • La version logicielle ci-dessus permet de modifier les règles pendant qu’on joue, ce qui va beaucoup plus loin que l’imaginait Post, en particulier avec la notion, non encore explorée à ce jour, de système de Post non déterministe...

          Addendum

          Les nouveaux programmes de collège incitent à faire programmer par les collégiens ce genre de système, de préférence avec un outil de programmation graphique. Voici la version Sofus :

          La grammaire transformationnelle est codée par un bloc fait de tests sur la prémisse et de conclusions à retourner dans chaque cas :

          Pour programmer le système de Post, on répète les opérations suivantes :

          • Ajouter à la fin du mot r, le suffixe calculé par la fonction tag appliquée à la première lettre du mot r ;
          • enlever les trois premières lettres de r se fait en remplaçant r par le mot commençant à la quatrième lettre et finissant à la fin ;
          • il n’y a plus qu’à ajouter le nouveau mot r en bas de l’affichage.

          En Sofus, tout le programme est ici :

          En fait, on peut même réaliser un logiciel de conjugaison à l’aide de ces techniques de découpage [11]. La fonction tag vue ci-dessus permet aussi de se lancer dans la cryptographie : On boucle sur les lettres du mot et on « tague » chacune par un texte qui va constituer le mot codé. Mais en dehors des babas fans du groupe Abba, on en vient vite à chercher des méthodes de cryptage plus efficaces que la fonction définie lettre par lettre.


          [1Suivant les recherches de Thurston sur la géométrie hyperbolique en dimension 3, on considère par exemple les matrices U et V suivantes :

          On vérifie par le calcul que le carré de la première matrice est le cube de la seconde. Ceci permet de simplifier des produits des matrices U et V comme UUVUVVVVUUV (en remplaçant par exemple VVV par UU). Il y a une centaine d’années, Axel Thue demandait s’il y avait un moyen de savoir sans effectuer les produits de matrices, si deux produits du type UUVVUVUUVVVUV et VVUVUUVVU sont égaux : Thue cherchait un algorithme permettant de comparer des produits de matrices. Cette question est connue sous le nom de problème du mot. Les opérations comme le remplacement de VVV par UU s’appellent des règles de réécriture. Le problème du mot a été un des sujets de recherche d’Alan Turing dans les années 1950. Mais dès le début des années 1920, Emil Post s’est intéressé au cas particulier des « systèmes semi-tuéens » (problème du mot pour les semi-groupes, cas où les matrices ne sont plus forcément inversibles). C’est dans le cadre de ces réflexions sur un problème de nature algébrique que Post a inventé le problème exposé ci-dessous.

          Emil Post était logicien, il cherchait avant tout à modéliser l’évolution des états internes d’un logicien lors de la rédaction d’une démonstration mathématique en logique propositionnelle : Une démonstration n’est jamais qu’une manipulation de chaînes de caractères, comme remplacer p∧(p ⇒ q) par p∧q. Aussi dans ces jeux de manipulation de chaînes de caractères, on appelle

          • axiome la chaîne de caractères initiale ;
          • règles (de production, pas de déduction) les étapes de l’algorithme appliqué à la chaîne de caractères) ;
          • théorèmes les productions successives (chaînes de caractères obtenues).

          Par la suite, Post est passé à autre chose, mais à la fin de la seconde guerre mondiale, presque en même temps et indépendamment l’un de l’autre, Emil Post et Andreï Markov (mathématicien soviétique) ont montré que les systèmes de réécriture sont Turing-complets.

          Une dizaine d’années plus tard, presque en même temps et indépendamment l’un de l’autre, Stephen Cole Kleene et Noam Chomsky ont fondé la théorie des langages sur des notions similaires, le théorème de Kleene et la grammaire générative et transformationnelle, respectivement.

          Avec l’algèbre, la logique, la calculabilité et la théorie des langages, le problème de Post est donc central en informatique théorique.

          [2car, alors qu’un système de tague modifie in situ une chaîne de caractères, la biosynthèse des protéines est effectuée par des ribosomes qui lisent une chaîne de caractères (l’ADN) et écrivent une autre chaîne de caractères (la protéine). pour autant,

          • la construction de la protéine par le ribosome est analogue au jeu ci-dessus, en assimilant les acides aminés aux perles qui sont pondues sur la droite de la figure (l’axiome représentant la protéine) ;
          • le ribosome étant lui-même fait d’acides nucléiques, est « écrit » dans la même langue que la chaîne de caractères qu’il lit (un peu comme dans le jeu ci-dessous) ;
          • la notion d’étiquette (biologie) est similaire à l’ajout de lettres à la fin d’un mot ; on touche là à la bioinformatique...
          • voir la typogénétique d’Hofstadter aussi.

          [3le mot est d’Emil Post, logicien, qui voulait ainsi modéliser le travail d’un logicien en train de rédiger les étapes successives d’une démonstration

          [4cela a pour effet de colorier la rangée d’œufs bleus alternativement en rouge et en vert, ce qui a à son tour pour effet de représenter par la couleur du premier œuf, la parité du nombre total d’œufs

          [5cela a pour effet de diviser par 2 le nombre d’œufs bleus, cette division ne se faisant que si le premier œuf est rouge, c’est-à-dire si le nombre d’œufs bleus était pair

          [6ce qui multiplie par 1,5 le nombre d’œufs bleus si celui-ci était impair, c’est-à-dire si le premier œuf était vert

          [7ici, le voisin de droite, c’est donc un 2-tag system puisque 2 œufs disparaissent à l’éclosion : Celui qui a éclot et son voisin.

          [8d’après un algorithme de Liesbeth de Mol

          [9parce que la programmation sans clavier utilise jQuery-UI qui entre parfois en conflit avec spip, et que cet article est rédigé en spip. La version en ligne n’utilise que jQuery, pas jQuery-UI...

          [10On peut aussi chercher des configurations non atteignables comme un Jardin d’Éden (automate cellulaire).

          [11Pour les verbes du premier groupe, on

          • extrait la racine verbale du verbe, en enlevant le « er » final, ce qui se fait en gardant le mot (initialement à l’infinitif) privé de ses 2 dernières lettres ;
          • boucle sur les personnes, en créant une phrase formée de
            • l’article (en fait un pronom) ;
            • un espace séparant l’article du verbe
            • la racine verbale
            • la terminaison (suffixe)

          Pour se faciliter la vie, on crée une liste de sujets (article) et une liste de terminaisons (suffixe) :

          Pour avoir la racine verbale on découpe le verbe à l’infinitif :

          Enfin la constitution de la phrase se fait à la façon Sofus, en ajoutant progressivement des morceaux de phrase par concaténations successives :

          On peut aussi demander le verbe par une entrée textuelle. Cela permet d’avoir des variantes comme

          je programme
          tu programmes
          elle programme
          nous programmons
          vous programmez
          elles programment

          Prolonger cette activité à des verbes des groupes 2 et 3 est un exercice intéressant sur les tests (sur l’avant-dernière lettre du verbe à l’infinitif).


          Commentaires

          Annonces

          Prochains rendez-vous de l’IREM

          Séminaire EDIM-IREM

          - Mercredi 8 mars 2017, 14h-18h, PTU, Saint-Denis, salle S23.6
          - Mercredi 12 avril 2017, 14h-18h, campus du Tampon
          - Mercredi 3 mai 2017, 14h-18h, PTU, Saint-Denis, salle S23.6
          - Mardi 13 juin 2017, 14h-18h, campus du Tampon
          - Mercredi 14 juin 2017, 14h-18h, PTU, Saint-Denis, salle S23.6

          Semaine des mathématiques

          Du 23 mars au 4 avril 2017 dans l’académie de la Réunion.


          Brèves

          À travers les labyrinthes : algorithmes et fourmis

          dimanche 1er septembre 2013

          Quand les chercheurs mettent au point des modèles d’optimisation et de recherche de plus court chemin qui s’inspirent du comportement de masse de colonies de fourmis...
          À écouter : Sur les Épaules de Darwin, émission diffusée sur France Inter samedi 31 août 2013.

          Rencontres Mondiales du Logiciel Libre à St-Joseph

          mardi 20 août 2013

          Les RMLLd se dérouleront pour la 2e fois à Saint-Joseph du 22 au 25 août.
          C’est une opportunité pour les élèves qui suivent la spécialité ISN et les passionnés d’informatique.

          Voici pour le samedi et le dimanche quelques interventions choisies :
          - http://2013.d.rmll.info/Raspberry-votre-ordinateur-au-format-carte-de-credit?lang=fr
          - http://2013.d.rmll.info/Materiel-libre-et-DIY?lang=fr
          - http://2013.d.rmll.info/Arduino-de-l-electronique-libre?lang=fr

          Noter aussi les conférences Art et Culture du dimanche, ainsi qu’une conférence plus engagée.

          Le programme complet se trouve ici. Une radio sera ouverte pour l’occasion.
          Des plaquettes à distribuer se trouvent ici.

          Hyper-vidéos pour l’algorithmique au lycée

          dimanche 19 août 2012

          Olivier Roizès, à la demande de l’ADIREM, a réalisé une collection d’hyper-vidéos de présentation de logiciels et environnements de programmation. Ces hyper-vidéos, c’est-à-dire des vidéos contenant des éléments clicables, devraient être utiles aux enseignants désireux de se familiariser avec Python, CaRMetal, R, Rurple, Scilab ou Xcas.

          Ouverture du SILO

          mardi 1er novembre 2011

          Le SILO (Science Informatique au Lycée : Oui !) est un espace collaboratif documentaire de partage et de formation collégiale, à destination des professeurs appelés à enseigner l’informatique au lycée.

          Une initiative du CNDP, de l’INRIA et de Pasc@line, à laquelle se sont associés SPECIF, fuscia, EPI et ePrep.

          Sur le Web : Site du SILO

          Introduction à la science informatique

          lundi 12 septembre 2011

          Le CRDP de Paris publie le premier ouvrage destiné aux professeurs chargés d’enseigner la nouvelle spécialité « Informatique et sciences du numérique » en Terminale S à la rentrée 2012. Cet ouvrage a été coordonné par Gilles Dowek, directeur de recherche à l’INRIA.

          Sur la création de la spécialité ISN, on pourra également consulter l’interview donnée au Café pédagogique par l’inspecteur général Robert Cabanne.

          Sur le Web : CRDP de Paris

          Deux publications sur l’algorithmique

          samedi 17 octobre 2009

          L’IREM d’Aix-Marseille publie une brochure de 73 pages, téléchargeable librement, intitulée Algorithmes et logique au lycée. Ces notions sont illustrées et déclinées sur des exercices du programme de spécialité mathématique en série L, mais sont adaptables aux programmes à venir.

          Le hors série thématique n° 37 du magazine Tangente, disponible actuellement en kiosque, s’intitule « Les algorithmes. Au cœur du raisonnement structuré ». Extrait de l’éditorial : « La rédaction de Tangente a conçu la quasi-totalité de ce hors série thématique pour qu’il puisse être lu par des élèves de Seconde ».

          Une carte mentale pour l’algorithmique

          jeudi 10 septembre 2009

          Sur son site, Jean-Jacques Dhénin a publié une carte mentale géante qui renvoie vers plus de 30 documents en ligne sur l’algorithmique. Tout ce qu’il faut — et même davantage — pour faire face au nouveau programme de Seconde !

          Un catalogue libre d’algorithmes pour le lycée

          dimanche 30 août 2009

          Guillaume Connan, de l’IREM de Nantes, publie un catalogue libre de 119 pages d’algorithmes pour le lycée. Sur son site très riche, on trouvera d’autres documents en rapport avec l’algorithmique, notamment sur l’utilisation des langages fonctionnels au lycée et sur la comparaison programmation fonctionnelle/programmation impérative.

          L’algorithmique à l’IREM de Lille

          vendredi 26 juin 2009

          Le groupe AMECMI de l’IREM de Lille vient de mettre en ligne des ressources importantes au service des professeurs de Seconde :

          - Algorithmique et programmation (Emmanuel Ostenne)
          - Bibliographie amoureuse de l’algorithmique (Alain Juhel)

          Statistiques

          Dernière mise à jour

          dimanche 26 mars 2017

          Publication

          735 Articles
          Aucun album photo
          128 Brèves
          11 Sites Web
          126 Auteurs

          Visites

          672 aujourd'hui
          1231 hier
          1967846 depuis le début
          48 visiteurs actuellement connectés