• Automates cellulaires
  • Description
  • Automates de dimension 1
    • Classes d'automate
      • Classification de Wolfram
      • Exercice
  • Automates de dimension 2
    • Le jeu de la vie
      • Exercice
      • Pour aller plus loin
    • Automates cellulaires réversibles
      • Automates réversibles de bloc
      • Exercice
  • Automates auto-réplicatifs
    • La boucle de Langton
      • Exercice
    • Pour aller plus loin
  • Conception
  • Vocabulaire
• Notes et références

Automates cellulaires

Comment des interactions simples entre des entités extrêmement simples peuvent-elles engendrer des comportements complexes, jusqu'à des mécanismes auto-reproducteurs ?

Les automates cellulaires sont des modèles abstraits simulant le fonctionnement des ordinateurs. Par là, ils sont à rapprocher des machines de Turing. Si cet aspect est important, ce n'est pas celui sur lequel nous allons nous concentrer dans le cadre de ce cours. C'est sur leurs capacités de modéliser des systèmes complexes que nous allons nous focaliser. Ces derniers sont constitués d’un grand nombre d’entités en interaction qui évoluent au cours du temps. Le comportement des entités dépend à la fois de l'environnement et des autres entités qu’elles peuvent observer localement autour d’elles. On peut citer différents exemples comme le trafic routier, les nuées d’oiseaux, l'occupation de nids d’abeille, le développement de tissus cellulaires ...

À partir de règles simples les automates cellulaires permettent de générer des évolutions extrêmement riches.

Les automates cellulaires ont été proposés dans les années 1950 par John von Neumann suite à une suggestion de son ami le mathématicien Stanislaw Ulam. Alors qu'il s'interrogeait sur comment concevoir une machine capable de s'auto-reproduire, Ulam l'orienta vers une question moins vaste : quelle organisation logique est suffisante pour un automate pour être capable de s'autoreproduire ?

Von Neumann fait alors le choix de considérer le problème dans un espace mathématique simple, métaphore du monde réel. L'espace est une grille régulière composée de cellules qui ont un état choisi dans un ensemble fini d'états possibles. L'évolution se fait à chaque pas de temps en fonction de règles locales.

Cette vision initiera tout un développement encore très actif autour des automates cellulaires, c'est ce que nous allons exposer partiellement dans la suite.

Description

Les automates cellulaires sont des machines à états finis évoluant sur une grille infinie, le plus souvent, et de dimension n. Les dimensions habituelles sont généralement 1 ou 2. La grille définit un espace discret et un voisinage pour chacune des cases de la grille. Cette grille peut être régulière ou non et les cases peuvent prendre différentes formes (carrée, hexagonale ....). On associe à chaque case de la grille une cellule, cette dernière va alors avoir un état. Le nouvel état est déterminé par l'état de la cellule considérée, le voisinage et une règle de transition. L'automate cellulaire évolue en fonction de ces modifications qui peuvent se faire de façon synchrone ou asynchrone. Dans ce qui suit nous considérerons uniquement le premier cas.

Soit

• L
  un réseau régulier (ses éléments sont des cellules) ;
• S
  un ensemble fini d’états ;
• N
  un ensemble fini d’indices de voisinage (de taille
  n
  ) tels que

• Une fonction de transition :
  f : S^n \rightarrow S
  ;
• Un automate cellulaire est défini par le 4-tuple :
  (L, S, N, f)
  ;
• Une configuration
  C_1 : L \rightarrow S
  est une fonction qui associe un état à chaque cellule du réseau ;
• Le rôle de la fonction de transition
  f
  est de changer
  C_i
  en
  C_{i+1}
  selon la relation :
  C_{i+1}(r) = f(\{C_i(j) | j \in N(r)\})
  , avec
  N(r)
  qui désigne l'ensemble des voisins de le cellule
  r
  .

Automates de dimension 1

Considérons un ruban infini des deux cotés, subdivisé en cellules. Chaque cellule pouvant prendre une valeur dans un ensemble fini. Par commodité de représentation on va transcrire ces valeurs en une couleur. Ainsi on va utiliser deux couleurs blanc et bleu :

Chaque cellule va alors changer de couleur en fonction de la couleur de ses voisines. L’évolution d'un automate cellulaire de dimension 1 est alors représenté par un diagramme espace-temps.

Si on défini on a la fonction de transition suivante : une cellule est coloriée en bleu au temps

Cela n'est pas sans rappeler les triangles de Sierpiński !

En effet certains automates exhibent des diagrammes espaces-temps fractaux.

Classes d'automate

Wolfram ¹ s'est penché sur le cas des automates de dimension 1 à deux états, en considérant le voisinage immédiat. Pour une case donnée il reste donc à définir l'évolution. On peut rapidement se convaincre qu'il n'y a que 8 états à considérer :

Il n’y a donc que

Dans son atlas, Wolfram énumère et étudie les différentes règles.

On peut déjà constater sur les exemples proposés la diversité de comportement de nos automates cellulaires. Le 126 nous produit une structure fractale alors que le 254 nous offre une pyramide noire.

En modifiant une seule transition pour créer la règle 250 vous obtenez une structure périodique.

La règle 30 est elle plus surprenante car elle nous propose un diagramme espace-temps étonnant.

Au début l'automate cellulaire semble se comporter de manière régulière et d'ailleurs cette impression subsiste si l'on considère la partie gauche du diagramme.

Sur la droite on voit apparaître des triangle de tailles différentes, sans une forme de régularité ou une "logique" sous-jacente. Wolfram a montré que le comportement de cet automate était chaotique. Des règles simples et déterministes peuvent engendrer le chaos !

Poursuivons encore l'exploration de ce bestiaire la règle 110 nous réserve des surprises. En effet l'automate correspondant à un comportement intéressant à la frontière du chaos. Si l'on regarde son évolution sur la droite il reste totalement blanc sur la droite. Sur la gauche, ce n'est pas la même chose.

Le motif bien qu'ayant l’air régulier, il apparait et disparait des séries de triangles blanc qui se propagennt et des bandes noires diagonales. Ces structures semblent interagir : elles apparaissent, se rencontrent, disparaissent. Cook a montré que cela constituait une machine universelle, cela implique que n'importe quel programme peut être simulé sur cet automate.

Classification de Wolfram

Ces classes sont encore discutées, néanmoins elles suffisent pour notre propos. Wolfram a proposé quatre classes de complexité pour les automates cellulaires en fonction leur diagramme espace-temps.

• La classe 1, le comportement est monotone, il produisent un motif homogène. Pratiquement toutes les configurations initiales conduisent à la même configuration fixe et homogène.
• La classe 2, le comportement est plus sophistiqué. Pratiquement toutes les configurations initiales conduisent à des configurations qui se répètent périodiquement. La périodicité constatée souvent ne fait que refléter la configuration initiale, néanmoins certains automates cellulaires de classe 2 ont des diagrammes espace-temps sans que la configuration initiale le soit.
• La classe 3, le comportement semble chaotique. Leurs diagrammes espace-temps semblent irréguliers. Ils ont généralement une grande sensibilité aux conditions initiales : une légère modification de la configuration initiale change fortement les diagrammes ou semble avoir des conséquences très lointaines.
• La classe 4, il y a émergence de structures localisées avec des interactions complexes. Ce type d'automate se rapproche fortement des définitions de la vie artificielle. Il y a émergence de structure.

Exercice

Réaliser en NetLogo une étude de ces automates à 1 dimension à 2 états. On écrira le programme le plus général possible auquel on fournira la règle et la situation initiale.

Automates de dimension 2

Un automate cellulaire de dimension 2 correspond à une description d'un univers de dimension 2 dont les lois sont déterministes et locales. L'espace est constitué d'un plan pavé de façon régulière par des polygones réguliers, le plus souvent. Dans le cas d'un plan euclidien, il s'agit alors soit de triangles équilatéraux, de carrés ou d'hexagones. Les cellules remplissent entièrement l'espace à 2 dimensions et le pavage est périodique,

Le jeu de la vie

Proposé par John H. Conway, il a été présenté à l'origine comme un jeu mathématique dans la chronique tenue par Martin Gardner du Scientific American. À la base, Conway s'est intéressé aux travaux de Von Neumann qui comme nous l'avons déjà évoqué cherchait à construire un automate auto-reproducteur. L'histoire raconte qu'il utilisait un jeu de Go pour rechercher les règles, et ensuite les pavés des couloirs. Il voulait être en mesure de proposer un automate présentant un comportement intéressant et capable de se dupliquer. Le premier objectif a largement été atteint comme nous pourrons le constater dans la suite, quant au second certes l'automate n'est pas auto-réplicateur mais il est possible de programmer un jeu de la vie avec un jeu de la vie !

L'espace considéré est une grille pavée de carrés. Chaque carré est une cellule qui peut peut être l'un des deux états possibles : vivant ou mort. Le voisinage considéré est celui de Moore d'ordre 1.

L'état d'une cellule à l'instant

• Une cellule morte ayant exactement trois voisines vivantes, passe de l'état mort à l'état vivant (naissance) ;
• Une cellule vivante ayant deux ou trois voisines vivantes, reste dans son état (survie) ;
• une cellule vivante, change d'état, si il y a : – moins de deux cellules voisines vivantes (mort par isolement) ; – plus de trois cellules voisines vivantes (mort par sur-population).

Le jeu de la vie génère une grande diversité de configuration et l'on voit émerger suivant les configurations, quatre configurations classiques :

Les structures stables

Si elles sont isolées, elles ne varient pas au cours du temps. Elles peuvent par contre être le résultat d'une évolution.

Les structures périodiques

Ce sont des structures qui reviennent dans leur configuration initiale, au bout d'un nombre fini de générations. Ce nombre défini la période, elle peut être plus ou moins grande.

L'exemple le plus simple est le clignotant . Il en existe des beaucoup plus sophistiqués.

Les vaisseaux

C'est un motif fini qui réapparaît au bout d'un certains nombres d'itération mais pas à sa place initiale.

Le planeur est l'exemple le plus connu (cf. ci-dessous). C'est le plus petit vaisseau du jeu de la vie : cinq cellules contenues dans un carré de trois cellules sur trois. Il se déplace d'une case en diagonale toutes les quatre générations.

Les mathusalems

Ce sont des structures qui "explosent" en structures stables. Le R-pentamino trouvé par Conway lui-même est un exemple. C'est d'ailleurs à partir de ce dernier que le planeur a été trouvé.

Système complexe La combinaison de structure amène une dimension supplémentaire, encore. Le jeu de la vie présente toute les caractéristiques d'un système complexe. Bien que les règles soient d'une simplicité absolue, on observe des comportements complexes et des caractérisques liées aux systèmes complexes : l'auto-organisation, l'émergence et une trajectoire non prévisible.

Ainsi lorsque l'on part d'une configuration aléatoire après un certains nombres d'itérations, le système ne présente plus une répartition aléatoire. Il y a des zones vides, des zones "calmes et stables" et d'autres encore en évolution. Cela témoigne d'une forme d'auto-organisation. L'émergence est elle présente dans les R-pentaminos qui génèrent des planeurs qui se déplacent dans l'espace sans que cela ait été spécifié/codé par les règles. On pourrait vouloir décrire le comportement global du système mathématiquement, mais cela s'avère difficile voire impossible, ainsi on conjecture qu'aucune méthode dans le cas d'une grille infinie ne sera plus efficace que la simulation.

Le jeu de la vie est irréversible. Il n'est pas possible de déterminer des règles permettant de déduire d'une configuration donnée au pas de temps

La combinaison de structure permet de générer des structures qui génèrent elles-même d'autres structures. C'est le cas des canons dont la partie principale se répète périodiquement, comme un oscillateur, et qui émet des vaisseaux à intervalle régulier. Le plus connu est celui de Gosper.

Dans le bestiaire du jeu de la vie ces structures ne sont pas anodines, elles permettent de répondre à une question que Conway s'était posé dès le début, la croissance peut-elle être infinie ? En effet, pour envisager construire une machine de Turing, il faut que cette condition soit respectée. Depuis cela a été réalisé. Plus amusant (?) encore, le jeu de la vie peut simuler le jeu de la vie !

YouTube

Exercice

Vous n'y couperez pas ! Vous devez programmer le jeu de la vie.

Plusieurs possibilités doivent être offertes à l'utilisateur. Vous devez commencer par concevoir un premier programme du jeu de la vie. Ce programme devra demander à l’utilisateur le taux d’occupation initial et s'il fait le choix d'une génération aléatoire de départ ou d'une configuration qu'il fournira soit à l'aide de l'interface, soit à l'aide d'un fichier. Ensuite, l’utilisateur pourra choisir si le programme fera évoluer la grille pas par pas, ou si la simulation sera effectuée pour un nombre de pas de temps donné (choisi par l’utilisateur) ou à l'infini. La simulation devra se dérouler sur un tore. Le programme devra alors pouvoir afficher, durant la simulation, une courbe présentant l’évolution du taux d’occupation de la grille en fonction du temps.

Les fichiers seront encodés sur le format lif 1.06. Vous pourrez en trouver une description ici et un zoo de structures sur le même site. Si d'aventure vous voulez tester une autre configuration dans un autre format, vous pouvez toujours utiliser le convertisseur de Adam Wolf and Matthew Beckler.

Pour aller plus loin

Vous pouvez chercher à détecter automatiquement une extinction, une structure stable, une structure périodique ou encore un vaisseau, sur un nombre de pas de temps maximal saisi par l’utilisateur. Pour les structures périodiques on indiquera la période, et pour les vaisseaux on indiquera la vitesse de déplacement sous la forme

Pour certaines configurations on arrive à

Automates cellulaires réversibles

On veut maintenant construire un automate qui puisse "remonter dans le temps" de façon déterministe. Les règles de transition d'un tel automate doivent donc être réversible. Nous l'avons déjà dit, le jeu de la vie n'est pas réversible. L'existence des jardins d'Eden en est la preuve. Nous allons donc considérer les automates réversibles de bloc.

Automates réversibles de bloc

Les automates réversibles de bloc sont des automates particuliers. Le pavage de l'espace est divisé en blocs ne se chevauchant pas. Cette division varie suivant les étapes de temps, la partition de l'espace n'est donc pas la même à

Un automate réversible de bloc est composé de :

• une grille régulière de cellules ;
• un ensemble fini d'états dans lesquels chaque cellule peut être ;
• une partition des cellules en une tesselation uniforme couvrant la grille et dans laquelle chaque élément de la partition formant un bloc ont la même taille et la même forme ;
• une règle de changement de partition après chaque pas de temps ;
• une règle de transition constituée d'une fonction qui prend en entrée une configuration d'états pour les cellules d'un même bloc et produit en sortie une autre affectation d'états pour les mêmes cellules.

À chaque pas de temps, la règle de transition est appliquée de façon synchrone à l'ensemble des blocs constituant la partition considérée et ensuite la règle de changement de partition est utilisée et le processus continu. La partition de l'espace défini un voisinage.

Dans la représentation de l'espace ci-dessus un voisinage de Margolus est défini. La partition de l'espace alterne entre deux configurations de blocs (2 x 2) délimitées soit par le tracé rouge, soit par le tracé bleu. Cette tesselation particulière va nous être utile dans la suite, pour construire un automate réversible. Auparavant définissons la notion de calcul réversible.

Un calcul informatique

Propriétés d'un voisinage de Margolus

Si vous considérez le voisinage proposé, si vous translatez verticalement ou horizontalement d'un nombre impair de cellule vous n'obtiendrez pas en général le même comportement, ce qui n'est pas le cas du jeu de la vie. Ceci est du à la structure par bloc.

De la même façon un décalage dans le temps d'un nombre impair modifie le comportement de l'automate puisque la tesselation a changé. Une configuration initiale évoluera différemment selon que l'on part à l'étape 0 ou à l'étape 1. Une configuration n'a de sens qu'avec sa tesselation.

L'isotropie est également généralement absente, en effet, le comportement variera si l'on effectue des rotations à 90°, sauf si la fonction de changement de bloc est invariante sous cette transformation.

Règles de transition dans un voisinage de Margolus

Chaque bloc est constitué de 4 cellules, de ce fait, une fonction de transition doit avoir 4 entrées et 4 sorties. Si l'on considère un automate à 2 états, cela nous

Il est possible de coder facilement les règles, ceci vous est laissé en exercice.

Exercice

Vous devez donc coder en Netlogo, un automate réversible de bloc, utilisant un voisinage de Margolus et permettant de fixer les règles, il faut donc déterminer un codage.

Vous étudierez en particulier la rotation à 90°. Elle consiste en une règle simple : lorsqu’il y a une unique cellule en vie dans un bloc alors elle tourne de 90°.

Sur la rotation à 90° vous testerez les translations spatiales et temporelles et rechercherez des structures stables, périodiques et des vaisseaux.

Automates auto-réplicatifs

Les êtres vivants sont des agrégats compliqués de composants simples et, selon toute théorie probabiliste ou thermodynamique raisonnable, ils sont très improbables. La seule chose qui explique ou atténue ce miracle est le fait qu’ils se reproduisent : si, par accident, il en apparaît un seul, alors les principes des probabilités ne s’appliquent plus et il s’en produit beaucoup. John von Neumann, Theory of Self-Reproducing Automata, 1966. ³

À la fin des années 40 et au début des années 1950, von Neumann s'est intéressé au problème des machines auto-réplicatrices et comme nous l'avons signalé dans la partie introductive de ce chapitre Stanislas Ulam lui proposa de simplifier le problème en étudiant cela dans un monde élémentaire, celui des automates.

Von Neumann a tout d'abord proposé un modèle de machine (le kinematon) capable de s'autorépliquer à partir de matériaux présents dans l'environnement et en utilisant un programme. Le kinematon (la machine) contient une auto-description que la machine interprète comme un programme mais constitue également un composant. Cette description est donc d'abord utilisée pour construire le réplicat et ensuite copiée pour que ce dernier contienne une auto-description.

Il est intéressant de préciser que cette description a été proposée avant la découverte de l'ADN et son mécanisme de réplication.

C'es ensuite que von Neumann sur les conseils d'Ulam a proposé un automate cellulaire auto-réplicateur. Von Neummann n’était pas complètement convaincu :

En axiomatisant les automates [autoréplicateurs] de cette manière, on (...) s'est résigné à ne pas expliquer comment ces éléments sont constitués de choses réelles, particulièrement comment ces éléments sont constitués de particules élémentaires ou même de molécules (...) on considérera simplement que des particules élémentaires dotées de certaines propriétés existent. La question à laquelle on espère répondre, ou au moins examiner, est : quels principes sont mis en œuvre dans l'organisation de ces molécules dans les êtres vivants fonctionnels (...) ³

L'automate d'origine comporte 29 états et utilise un voisinage de 5 cellules. Chaque cellule est un automate à états finis. La taille de l'automate est de l'ordre de 200 000 cellules. Ces 29 états pour simuler des fils et le transport des signaux. Un enregistrement formé par une succession de cellules encode une suite d'actions que la structure doit effectuer. À l'aide d'une tête d'écriture, cette structure peut créer de nouvelles cellules, permettant ainsi une réplication d'elle-même et de l'enregistrement. Le modèle n'était que théorique. Ce n'est qu'en 1995 qu'une configuration fonctionnelle a été proposée par Renato Nobili et Umberto Pesavento⁴. En 1968, Edgar F. Codd simplifia largement l'automate en utilisant 8 états.

Avant de nous intéresser à la boucle de Langton, revenons sur le jeu de la vie ou l'un de ses dérivés. HighLife a été proposé en 1994 par Nathan Thompson. L'intérêt d'HighLife est qu'il existe une structure "simple" capable de se répliquer à l'identique

Les règles sont les suivantes : une cellule morte naît à l'étape suivante si elle est entourée de 3 ou 6 voisines vivantes, une cellule vivante survit à l'étape suivante si elle est entourée de deux ou trois cellules vivantes. Ces règles sont très proches de celles du jeu de la vie (seule la condition de naissance pour 6 cellules vivantes voisines diffère). Cet automate est néanmoins semble t-il moins riche.

Pour terminer sur ce sujet il nous faut évoquer la configuration Gemini du jeux de la vie. C'est un vaisseau qui se déplace de façon oblique il a été proposé par Andrew J. Wade en 2010. Il se déplace de 5120 cellules verticalement et de 1024 cellules horizontalement toutes les 33 699 586 générations. En avançant, cette structure crée une copie d'elle-même en détruisant la précédente.

Terminons ce paragraphe sur un clin d’œil.

#include<stdio.h>
main(){char*c="\\\"#include<stdio.h>%cmain(){char*c=%c%c%c%.
102s%cn%c ;printf(c+2,c[102],c[1],*c,*c,c,*c,c[1]) ;exit(0) ;}
\n" ;printf(c+2,c[102],c[1],*c,*c,c,*c,c[1]) ;exit(0) ;}

La boucle de Langton

L'idée de von Neumann était très ambitieuse dans sa volonté de réaliser un système universel pour lequel l'auto-réplication est vue comme une condition nécessaire du mécanisme de construction qu'il peut réaliser. La complexité de l'automate qui en a découlé a poussé d'autres chercheurs a tenter de le simplifier. Ainsi Codd a proposé un automate à 8 états en 1968 mais comportant 283 126 588 cellules.

À la fin des années 1970, Christopher Langton a pris le problème dans l'autre sens en tentant de définir un automate cellulaire le plus simple possible ayant certes perdu le caractère d'universalité mais étant capable uniquement d'auto-réplication, forme de condition suffisante. Il s'est inspiré de l'émetteur périodique de Codd qui est constitué d'une suite de cellule formant un signal, le tout entouré par une membrane. On pourra y voir, en passant, des liens avec la vision de Varela. Langton a donc conçu un automate cellulaire comportant une structure dont les composants constituent l'information nécessaire à sa propre réplication. Si, Von Neumann, Codd dans leurs propositions utilisent une tête de lecture en quelque sorte, la encore une analogie se dégage avec la machine de Turing, Langton lui s'en affranchit. La description de la boucle de Langton est simple :

• une structure à la fois elle-même et codage d'elle-même ;
• huit états et vingt-neuf règles ;
• une boucle entourée d'une membrane à l'intérieur de laquelle le flux d'information permettant la réplication circule.

  2 2 2 2 2 2 2 2
2 1 7 0 1 4 0 1 4 2
2 0 2 2 2 2 2 2 0 2
2 7 2         2 1 2
2 1 2         2 1 2
2 0 2         2 1 2
2 7 2         2 1 2
2 1 2 2 2 2 2 2 1 2 2 2 2 2
2 0 7 1 0 7 1 0 7 1 1 1 1 1
  2 2 2 2 2 2 2 2 2 2 2 2 2

• la membrane est formée des cellules dans l'état 2 ;
• les cellules internes contiennent l'information de réplication
  • Les séquences 7-0 et 4-0 se propagent vers la queue ;
  • les séquences 7-0 prolongent la queue ;
  • les séquences 4-0 construisent un angle droit vers la gauche. La séquence auto-réplicatrice est la suivante :

7 0 - 7 0 - 7 0 - 7 0 - 7 0 - 7 0 - 4 0 - 4 0

Les 6 7 0 allongent donc la queue et les 2 4 - 0 construisent l'angle droit. Une règle bloque l'évolution quand il n'y a plus assez d'espace.

Exercice

Vous coderez la boucle de Langton en Processing ou NetLogo. Pour cela vous trouverez les règles ici et la description de ces règles [là] (https://github.com/gollygang/ruletablerepository/wiki/TheFormat). Pour une fois il sera probablement plus facile de faire le programme avec Processing. Voici une classe permettant de charger le fichier de règles. N'oubliez pas que les fichiers de données vont dans un répertoire data du sketch Processing.

Pour aller plus loin

L'automate de Langton et ses améliorations comme celle proposée par Byl sont très élégantes, néanmoins il manque un point essentiel, si l'on considère le point de vue de von Neumann : le codage doit permettre l'auto-réplication, mais aussi la création d’autres structures. Le code (génome) de nos configurations doit pouvoir évoluer ! Seule une telle condition permet de générer de la diversité et de la nouveauté.

Conception

Vocabulaire

Structures stables : ensemble de cellules qui n'évoluent plus.

Structures périodiques : ensemble de cellules qui se transforment de manière cyclique. Plusieurs motifs sont observés avant de revenir au motif initial.

Point fixe : un automate a atteint un point fixe lorsqu'il ne change plus de configuration quelque soit les itérations suivantes.

Jardin d'Eden : configuration pour laquelle il n'existe pas de configuration antérieure.

Densité : elle est mesurée par rapport à un état de chaque cellule, c'est donc le nombre de cellules d'un état donné sur le nombre total de cellules.

Synchrone : l'évolution d'un automate est synchrone lorsque chaque cellule de l’automate est mise à jour à chaque itération.

Asynchrone : une ou plusieurs cellules sont mises à jour mais pas la totalité lors d'une itération.

α-asynchronisme : à chaque itération chaque cellule est mise à jour avec une probabilité α.

Asynchronisme total : à chaque itération une seule cellule, choisie aléatoirement, est mise à jour. Il existe deux types d’asynchronisme total : (1) à mémoire : si l'automate possède

n

cellules, alors on conserve une trace des cellules mises à jour de sorte que durant toutes les

n

itérations, chaque cellule n’est mise à jour qu’une seule fois. (2) Sans mémoire : à chaque itération une cellule est choisie aléatoirement sans tenir compte du passé.

Robuste : un automate est dit robuste au sens du synchronisme s'il conserve ses propriétés quel que soit le type de synchronisme / asynchronisme choisi.

Isotropie : TODO

Réplication : un système est réplicateur s’il génère des entités identiques entre elles, mais différentes du système lui-même.

Copie : il y a copie quand un système génère des entités à lui-même.

Autoreproduction : "lorsque par un processus couplé à son propre processus de production une unité en produit une autre dotée d’une organisation semblable à la sienne" (Varela). L’autoproduction est vue comme un moment de l’autopoïese. Cette liaison entre le processus de fonctionnement et le mécanisme de production est une « clôture opérationnelle ». On parlera d’autoproduction des systèmes biologiques et d’autoréplication des systèmes artificiels.

Autoréplication : tout système doté d’une description de lui-même capable à la fois de l’interpréter et de la dupliquer.

Notes et références