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 <span class="base64" title="PGNvZGUgY2xhc3M9InNwaXBfY29kZSBzcGlwX2NvZGVfaW5saW5lIiBkaXI9Imx0ciI+c2VxIDEgMjA8L2NvZGU+"></span>; 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.
Commentaires