Note de lecture : Philosophy and Simulation (II)

Chapitre 2 : automates cellulaires et modèles de flux.

Dans le premier chapitre, Manuel DeLanda nous avait décrit une série de phénomènes faisant entrer en jeu des mécanismes d’émergence. Il fallait retenir de ce chapitre qu’à l’intérieur d’un tel phénomène, le mécanisme pouvaient concerner :

  • des propriétés actuelles du système étudié,
  • des capacités potentielles du système étudié,
  • et des tendances virtuelles du système étudié.

D’une part, on caractérisait alors le phénomène d’émergence par une relation particulière entre les parties et le tout du système, impliquant un changement d’échelle, tel que 1) le comportement du tout était relativement indifférent au comportement individuel des parties et 2) le comportement étudié à l’échelle du tout est impossible à déduire à partir de l’échelle des parties. D’autre part, nous devions y introduire une causalité indépendante de tout mécanisme qu’on expliquait alors à travers la mise au jour d’un espace de possibilités, structuré autour de singularités, toutes à la fois indépendantes et cependant inexistantes sans les gradients observés.

C’est l’ensemble de ces caractéristiques qu’il s’agit de retrouver non plus déduits à partir des phénomènes empiriques observables mais dans le cadre d’une représentation théorique autonome. Autrement dit, abstraction faite de tout phénomène réel, peut-on produire une représentation abstraite, formelle et théorique, qui produise par elle-même, à l’intérieur de son cadre représentatif, des phénomènes d’émergences.

Là encore quelques définitions préalables seront nécessaires.

Automate fini (abusivement appelé automate à états finis) : machine qui effectue un calcul qui consiste à passer d’un état à un autre dans une séquence précise et sans résultat intermédiaire. Soit l’exemple fameux de l’homme (H), du loup (L), de la chèvre (C) et de la salade (S) sur la rive d’une rivière et devant prendre une embarcation à deux places, en évitant bien sûr que le loup et la chèvre ne se retrouvent seul ou que la chèvre ne soit laissé à elle-même (ou avec le loup) devant la salade.

L’image ci-contre donne la résolution du problème et illustre ce qu’est un automate fini.

Source : Site WWW de Laurent Bloch

Pour lire la solution, précisons que l’homme fait chaque traversée, que le passager qui l’accompagne est notée sur les flèches de transition sauf si l’homme traverse seul, que le tiret sépare la rive droite de la rive gauche et que la bifurcation au milieu du chemin représente une alternative.

Automate cellulaire « consiste en une grille régulière de « cellules » contenant chacune un « état » choisi parmi un ensemble fini et qui peut évoluer au cours du temps. L’état d’une cellule au temps t+1 est fonction de l’état au temps t d’un nombre fini de cellules appelé son « voisinage ». À chaque nouvelle unité de temps, les mêmes règles sont appliquées simultanément à toutes les cellules de la grille, produisant une nouvelle « génération » de cellules dépendant entièrement de la génération précédente. » (Source Wikipédia). Vous aurez deviné que la cellule correspond à un automate fini.

Le Jeu de la Vie : est un exemple d’automate cellulaire. Les cellules sont des rectangles, soient 8 voisins pour une cellule. Il n’y a que deux états possibles pour la cellule : soit « vivante », soit « morte » (soit 1, soit 0) et les règles de transistion sont simples : 1) si la cellule est vivante et entourée par deux ou trois cellules vivantes, elle reste en vie à la génération suivante, sinon elle meurt 2) si la cellule est morte et entourée par exactement trois cellules vivantes, elle naît à la génération suivante.

Un gaz sur réseau « est un type d’automate cellulaire destiné à simuler le comportement d’un fluide. Un gaz sur réseau modélise l’espace sous le forme d’un réseau à deux ou trois dimensions. Le fluide est modélisé par des particules qui peuvent se déplacer entre les nœuds du réseau ; ces particules sont considérées comme ayant toutes la même masse.
Chaque itération de l’automate cellulaire procède en deux phases : 1) une phase de propagation : les particules possédant une vitesse non nulle se déplacent vers un nœud adjacent, suivant les mailles du réseau ; 2) une phase de collision : si plusieurs particules arrivent sur le même nœud, leur nouvelle direction est déterminée par des règles de collision. Ces règles conservent le nombre de particules, la quantité de mouvement et l’énergie avant et après les collisions. » (Source Wikipedia)

Machine de Turing : est une machine abstraite sensée reproduire les mécanismes d’un calcul, c’est-à-dire reproduire un algorithme. Elle consiste en un ruban où sont écrits des mots dans un alphabet que la machine peut comprendre, une tête de lecture qui lit le ruban case par case (de gauche à droite et de droite à gauche) puis cette tête est aussi susceptible d’écrire sur le ruban. Pour cela elle utilise une table d’action qui indique selon quelle règle tel symbole écrit.

Machine de Turing universelle : la table d’action d’une machine de Turing peut elle-même être encodée sur le ruban suivie des données sur lesquelles elle s’applique. Autrement dit, le programme peut être traité comme un ensemble de données exécutables. Ou encore, il est possible de concevoir une machine de Turing universelle capable de simuler toutes les machines de Turing à usage (ou programme) unique. Les ordinateurs actuels, en tant qu’ils chargent en mémoire des programmes qu’ils exécutent ensuite, sont des approximations des machines de Turing universelles.

Les définitions reprises ici ne sont pas toutes exactement celles formulées par DeLanda et il a le bon goût de les disperser au fil de l’argumentaire. Que va-t-il montrer ?

Source : Wikipédia

En s’appuyant sur le Jeu de la Vie, il nous invite à considérer que des tendances émergent dans le comportement des cellules. Tendance à rester en vie : après quelques générations et quelquesoit la distribution de départ, des cellules se regroupent par 4 pour se maintenir en vie. Tendance à osciller : de la même façon on observe à travers un cycle de transistions, un groupe de cellules se mettant à « clignoter », c’est-à-dire passer d’un état vivant à un état mort. Tendance à se « déplacer » : ce ne sont pas les cellules qui se déplacent mais l’état vivant ou mort peut être observé comme transitant d’un groupe de cellules à un autre selon la même progression. On observe alors ce qu’on appelle des vaisseaux. Des capacités également peuvent émerger. En effet, soient deux planeurs (type de vaisseau le plus simple en forme de V), on sait qu’il existe 73 façons pour eux d’entrer en collision. Dans 28 de ces cas, on obtient une annihilation mutuelle, dans 6 cas, on obtient un bloc, dans 3 cas, on obtient un clignoteur, dans 2 cas, il ne subsiste qu’un planeur. Le reste des cas est aléatoire. Soit maintenant une collision entre 13 planeurs, se constitue alors ce qu’on appelle un « canon à planeurs », c’est-à-dire une production ininterrompue de planeurs dans une unique direction. Dans ce cas, on observe que des capacités émergentes produisent à une échelle supérieure une autre capacité émergente. Toutefois, à cette échelle, un peu d’aide de la part des concepteurs du jeu est nécessaire.

Est-il possible de passer à une échelle supérieure autrement que par l’unique voie d’une conception extrinsèque ? Dans le Jeu de la Vie, nous avons affaire à des automates finis, c’est-à-dire à des automates qui passent d’un état à un autre sans état intermédiaire. Pour qu’un automate puisse prendre en compte un de ses états intermédiaires, il doit pouvoir fournir un mécanisme de mémorisation. C’est le cas de la machine de Turing. Toute la question consiste alors à savoir si on peut construire une machine de Turing avec un automate cellulaire. Plus précisément, la question est de savoir si la machine de Turing peut émerger à partir de comportements émergents dans les automates cellulaires. Si la réponse est oui, alors on prouvera le passage à l’échelle supérieure. La démonstration est quelque peu complexe mais est acquise depuis de nombreuses années. DeLanda s’en autorise pour ne nous parler que de la création d’une porte logique ET qui avec la porte logique NON constitue la brique essentielle qui va permettre de construire un registre d’état faisant fonction de mémoire. C’est ainsi qu’en associant « un canon à planeurs » et un « mangeur » (une capacité consistant en ce qu’une forme entrant en collision avec une autre l’annihile sans rien changer en elle) il est possible de créer un comportement logique ET dans l’automate. Le canon est pointé dans la direction du mangeur de telle sorte qu’il s’y annihilera de toute façon. Mais perpendiculairement à lui, on positionne deux autres canons à planeurs qui agissent comme les entrées de la porte ET. Lorsque l’état simultané de ces deux canons est à 1, la collision du premier d’entre eux avec le canon principal (lui-même à 1 au point de collision) crée un trou (état à zéro) par lequel le second peut alors passer. Toute autre configuration de collision n’étant pas capable de laisser passer un des deux canons perpendiculaires, c’est bien la porte ET qui est ainsi simulée.

Enfin, il reste à prouver qu’il existe dans le cadre des automates cellulaires l’équivalent d’une causalité indépendante de tout mécanisme. Ce qui revient à se demander quelle est l’espace de possibilités d’un automate cellulaire, c’est-à-dire s’il est possible d’extraire des singularités parmi toutes les règles de transition possibles dans une cellule en relation avec son voisinage. On distingue donc deux espaces : 1) un espace de voisinage calculé à partir des dimensions de l’automate. Pour un automate cellulaire de dimension 1, c’est-à-dire une ligne, on compte deux voisins plus la cellule elle-même. Ce qui nous donne pour deux états possibles par cellules, 8 motifs possibles (23). 2) la taille de cet espace étant donné, on applique à son ensemble la possibilité d’avoir deux états, ce qui donne 256 règles de transition possibles (28). Si on considère l’automate cellulaire impliqué dans le Jeu de la Vie, qui correspond à une grille sur deux dimensions, chaque cellule entourée de 8 voisines et susceptible de 2 états uniquement, on aurait 29 motifs possibles, soit 2512 règles possibles (soit environ 1,34 suivi de 154 zéros). En restant sur le cas d’un automate d’une unique dimension et pour chacune des règles, on procède à plusieurs distributions aléatoires de motifs et on observe que l’évolution de l’automate finit par se stabiliser autour de motifs particuliers au bout de nombreuses générations pour des classes de règles. Il y a ainsi de nombreuses règles qui tendent à fixer les motifs dans un état statique (classe I), il en existent d’autres qui tendent à faire osciller les motifs (classe II), il en existe une troisième qui produit des formes aléatoires (classe III) et il existe enfin une quatrième (classe IV) qui est suscpetible de produire des figures complexes de mouvement comme le planeur du Jeu de la Vie. Ces quatres classes sont les singularités qui structurent l’espace de possibilité de l’automate.

Cela ne nous renseigne pas sur la manière dont ces singularités se distribuent. En effet, contrairement à l’espace des phases d’un orage, l’espace est ici discret, c’est-à dire discontinu et non topologique. Une manière de surmonter cette difficulté consiste à ranger les règles d’après leur ressemblance. On part d’un minimum constitué par des règles homogènes entre elles et d’un maximum rempli par des règles les plus hétérogènes entre elles. Puis on remplit l’espace intermédiaire par une hétérogénisation croissante des règles. Il apparaît alors que la classe IV est non seulement prise en sandwich entre les règles de classe II et III mais qu’elles occupent également une zone plus petite, indice de leur rareté.

Une erreur fréquente consiste à confondre la détermination de l’espace des possibilités avec un déterminisme qui le parcours, fût-il probabiliste. Ainsi, inéluctablement, une machine de Turing émergerait à partir du Jeu de la Vie parce qu’il faut bien que toutes les possibilités de l’espace soient parcourues, fût-ce au-delà de nos capacités de calcul. Rien n’est moins vrai. Une machine de Turing n’est possible dans ce contexte qu’après des heures et des heures d’intervention sur les configuration de l’automate et d’exploitation de son espace des possibilités. En faisant cette erreur, on méconnaît la différence de nature entre une causalité mécanique et une causalité non mécanique, on s’empêche de penser adéquatement la seconde. Et puisqu’à partir du Jeu de la Vie, on peut concevoir non seulement une machine de Turing mais encore une machine de Turing universelle, on risque de penser en fin de course que le monde lui-même est un automate géant. En effet, une machine de Turing universelle ayant la propriété de simuler n’importe quel machine de Turing simple, elle fonde en théorie la possibité de toute simulation informatique. Ce ne serait pas la première fois qu’on chercherait à prêter à un fondement mathématique une singulière prétention à la fondation des choses. Tant qu’on en reste au Jeu de la Vie, ce n’est jamais que par analogie qu’on observe des blocs restant en vie, des oscillateurs passant de vie à trépas et autres sortes de canons à planeurs. Il suffit d’appeler vie l’état 1 et mort l’état 0, et vous nommez des phénomènes de représentation mathématique pure d’après les catégories de la vie. Si on inverse les termes (1 pour mort et 0 pour vie), on aurait aussi bien le Jeu des Zombies. Là où les automates cellulaires sont devenus de réels centres d’intérêt pour les scientifiques, c’est lorsqu’on a pu en concevoir qui ne simulait toujours rien de directement empirique mais d’autres type de représentation mathématiques et, particulièrement des équations différentielles.

Les automates de gaz sur réseau sont de cette famille d’automates cellulaires capables de simuler les équations différentielles employées pour étudier la dynamique des fluides, celles précisément employées pour étudier les phénomènes décrits au premier chapitre. Plus précisément, s’il fallait distinguer trois échelles, une première macroscopique qui étudie des masses d’eau et d’air en relation avec des gradients de températures et de pression, une seconde microscopique qui considère les molécules d’eau en mouvement et entrant en collision les unes avec les autres, et une troisième, atomique, qui rendrait compte de la stabilité des atomes en leur composants fondamentaux, l’automate de gaz sur réseau correspond à la seconde échelle qui est celle de la mécanique statistique. On notera trois différences de ce type d’automates avec ceux du type du jeu de la vie.

  1. les cellules ne représentent pas chaque molécule que l’on veut étudier mais sont le terme d’un processus de moyennisation typiquement statistique.
  2. Dans le Jeu de la Vie, avant d’avoir un canon à planeurs, il faut déjà que des planeurs aient pu émerger. Et les planeurs eux-mêmes dépendent de stades antérieurs d’évolution du Jeu. Autrement dit, il existe dans le Jeu de la Vie une flèche du temps qu’on doit exclure de l’automate de gaz en réseau puisqu’à cette échelle physique, les phénomènes sont réversibles. Ceci n’empêche pas que c’est à cet automate qu’on demandera de simuler des phénomènes (thermodynamiques) qui incluent la flèche du temps comme émergence.
  3. C’est là le troisième point. Ce que les règles spécifient, mouvement et énergie des cellules, ne sont pas productrices d’émergences en elles-même. C’est à l’échelle macroscopique, celui des masses d’eau et d’air constituées, qu’on observe des mouvements d’ensemble irréversibles.

Cliquez sur l’image si rien ne se passe.
Source : Wikipédia (en)

On retiendra donc que la simulation informatique ne commence réellement qu’à partir du moment où il devient possible d’établir ce que les mathématiciens appellent un isomorphisme entre le comportement des automates cellulaires et celui d’équations différentielles. Isomorphisme est un terme théorique qui prouve d’un point de vue scientifique que la « ressemblance » de comportement n’est pas le fait du hasard mais s’inclut dans la démarche scientifique. Qui plus est, la simulation apporte à la démarche scientifique une autre dimension. En effet, les équations différentielles qui expliquent la formation de cellules de convection à l’échelle macroscopique ne fournissent aucune informations sur l’échelle microscopique des molécules d’eau qui sert de substrat. L’automate de gaz sur réseau reproduit le comportement des équations mais est entièrement construit au niveau microscopique dont il reprend les caractéristiques physiques : uniformité, localité, réversibilité, conservation et symétrie. On voit donc que pour produire un isomorphisme sur une échelle émergente, on doit préalablement construire un autre isomorphisme relatif à l’échelle substrate. Enfin, en ayant la possibilité par exemple de multiplier des états de départ et d’observer si les résultats finaux sont identiques, la simulation informatique permet de mesurer l’évolution du processus simulé. C’est encore une propriété qu’on ne peut demander aux seules équations différentielles. On voit ici que ce n’est pas seulement la théorie formelle qui est simulée mais également la pratique expérimentale. En sorte que la simulation se situe entre les deux.

À suivre…

Publicités

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s