PLAN

REMERCIEMENTS. 3

INTRODUCTION.. 4

I. UNE BREVE HISTOIRE DES AUTOMATES CELLULAIRES. 6

1. La naissance des automates cellulaires. 6

L’idée de départ de von Neumann et d’Ulam.. 6

Le problème de l’auto-reproduction. 9

2. Un nouvel axe de recherche : le Jeu de la Vie. 13

Un univers à explorer 13

Recherche scientifique ou simple passion ?. 15

La calculabilité et la constructibilité universelle dans le Jeu de la Vie. 17

3. L’exploration de l’espace des automates cellulaires. 19

Les recherches se dirigent vers la physique. 19

Les généralisations de Life. 21

Le renouveau. 22

II. LA CONSTRUCTION D’UNE THEORIE.. 24

1. Définir le paradigme des AC.. 24

Définitions de base. 24

Interaction des cellules au sein des configurations. 29

La transmission de l’information. 30

2. La calculabilité et la constructibilité universelle. 31

La calculabilité. 32

La constructibilité. 35

3. Problèmes fondamentaux de la théorie des AC.. 38

La classification des AC.. 38

L’hypothèse de Langton. 40

III. LES ENJEUX EPISTEMOLOGIQUES. 43

1. Au cœur de la physique. 43

La question de la symétrie. 43

Étude d’un exemple  : le modèle d’Ising. 49

La relation discret / continu au cœur d’une épistémologie de la modélisation. 51

2. Au cœur de la biologie. 54

Le problème de l’auto-reproduction et le fonctionnement des cellules. 54

Qu’est-ce que la vie ?. 57

3. La compréhension des phénomènes d’émergence. 60

Réductionnisme et émergence. 60

Le concept de loi 63

La genèse des formes. 65

CONCLUSION.. 68

REFERENCES BIBLIOGRAPHIQUES. 71

ANNEXES. 75

REMERCIEMENTS

Je remercie très sincèrement M. Mosconi pour la confiance qu’il m’a accordée en acceptant de superviser ce travail. Son enseignement a su susciter mon intérêt pour de nombreuses questions de philosophie des sciences qui se retrouvent dans ce mémoire. La patience, l’écoute et l’estime dont il a su faire preuve tout au long de l’année ont représenté une aide précieuse dans cette recherche.

Je suis également reconnaissant à M. Dubucs pour ses conseils judicieux, pour ses recommandations auprès de chercheurs et pour m’avoir prêté l’ouvrage d’(archi)-référence que constitue le Poundstone. Je remercie de même Olivier Sigaud pour sa relecture attentive et ses questions stimulantes.

J’exprime également une grande reconnaissance à l’égard des chercheurs qui m’ont accordé de leur temps, soit au cours d’entretiens comme l’ont fait MM. Yunès[1], Morvan[2] et Heudin[3], ou par messagerie électronique comme l’ont fait MM. Narbel[4], Dowek[5] et Mazoyer[6]. Leurs conseils et références ont été déterminants pour l’orientation de nos recherches et leur soutien moral a constitué une source d’énergie indispensable.

INTRODUCTION

« - Je te montrerai donc [Glaucon], si tu veux bien regarder, que parmi les objets de la sensation les uns n’invitent point l’esprit à l’examen, parce que les sens suffisent à en juger, tandis que les autres l’y invitent instamment, parce que, la sensation, à leur sujet, ne donne rien de sain.

- Tu parles sans doute des objets vus dans le lointain et des dessins en perspective.

- Tu n’as pas du tout compris ce que je veux dire.

- De quoi donc veux-tu parler ? demanda-t-il.

- Par objets ne provoquant point l’examen, répondis-je, j’entends ceux qui ne donnent pas lieu, en même temps, à deux sensations opposées ; et je considère ceux qui donnent lieu comme provoquant l’examen, puisque, qu’on les perçoive de près ou de loin, les sens n’indiquent pas qu’ils soient ceci plutôt que le contraire. »

Platon, La République, [523-524]

L’exposé qui suit a pour but de présenter une classe de modèles abstraits appelés ‘automates cellulaires’ (AC). Le nom même d’automate cellulaire peut sonner comme une oxymore. D’un côté le mot ‘automate’ suggère que notre étude portera sur l’artificiel, le mécanique, le logique, le prévisible et de l’autre côté le mot ‘cellulaire’ renvoie au naturel, à la biologie et au vivant et donc à l’imprévisible. Comment deux concepts aussi opposés peuvent-ils s’associer au sein d’un même nom pour désigner un objet ?

            Cette association de termes opposés pour désigner un objet ne doit pas nous effrayer mais bien au contraire, comme le suggèrent les enseignements de Platon, constituer une invitation au questionnement. C’est à un tel examen que nous allons ici procéder. La difficulté principale dans la constitution d’une recherche sur les AC est que le nombre d’ouvrages de référence se comptent sur les doigts de la main. En France, la communauté des chercheurs qui y consacrent leur travail est de même extrêmement réduite ; le contact restant heureusement possible grâce à l’Internet. Le nombre d’articles scientifiques consacrés au sujet est relativement important, mais se trouve disséminé dans de nombreuses revues et actes de conférences différents, ce qui ne facilite pas la tâche. Notre travail a demandé un effort particulier pour trouver les informations pertinentes, puis pour les synthétiser afin d’en faire le point de départ d’une réflexion sur un domaine particulier de l’activité scientifique. Nous avons conscience du fait que ce travail de regroupement de l’information est partiel et que nous avons oublié (parfois sciemment) de parler de certains sujets.

La première partie de l’exposé retracera un historique des automates cellulaires, depuis leur invention par Ulam et von Neumann jusqu’aux développements plus récents. Nous nous intéresserons dans la seconde partie à la théorie des automates cellulaires, en essayant de nous limiter aux traits essentiels du domaine. Enfin, forts des repères acquis dans les deux parties précédentes nous aborderons dans la troisième partie une sélection de problèmes épistémologiques, pour conclure en nous demandant dans quelle mesure la compréhension des automates cellulaires peut représenter un enjeu.

I. UNE BREVE HISTOIRE DES AUTOMATES CELLULAIRES

Cette première partie retrace l’évolution des automates cellulaires depuis leur création jusqu’à nos jours. Nous avons distingué trois périodes essentielles dans cette brève histoire des automates cellulaires : leur création, qui fut une retombée féconde des travaux de von Neumann et d’Ulam sur l’auto-reproduction ; le développement du ‘Jeu de la Vie’ et enfin les explorations d’espaces d’automates cellulaires, qui visent à une compréhension globale du monde des AC.

1. La naissance des automates cellulaires

Les automates cellulaires ont été inventés par Stanislaw Ulam (1909-1984) et John von Neumann (1903-1957) à la fin des années 40 au Los Alamos National Laboratory (Etats-Unis) ( cf. Photos en ANNEXE A).

L’idée de départ de von Neumann et d’Ulam

Von Neumann est indiscutablement un grand génie du XX^e siècle, bien que ses travaux ne soient pas très connus du grand public. Le nombre de domaines auxquels il apporta des contributions décisives ne peut que laisser admiratif. Il fut un des pionniers dans la conception des ordinateurs, sa « Théorie des jeux » est un outil toujours utilisé par les décideurs dans les domaines économiques et militaires, il fit des avancées majeures en mécanique quantique et en physique nucléaire. Né à Budapest, en Hongrie, le 3 décembre 1903, il est souvent dépeint comme un génie précoce, capable de diviser mentalement deux nombres de huit chiffres. A l’age de 20 ans, von Neumann publia une définition de nombres ordinaux qui est toujours utilisée de nos jours. A l’âge de 25 ans, il découvrit que les états des systèmes quantiques pouvaient être représentés par des vecteurs d’un espace abstrait de dimension infinie. Il émigra aux Etats-Unis en 1931 et devint professeur de mathématiques à l’université de Princeton. Parallèlement à ses recherches fondamentales sur la logique mathématique, ses travaux de mathématiques allaient s’orienter vers une voie plus appliquée et durant les années 30, il allait travailler sur des modèles idéalisés de confrontations entre acteurs rationnels et donner ainsi naissance à la ‘théorie des jeux’. Durant la deuxième guerre mondiale, von Neumann dirigea la conception des premiers ordinateurs destinés à l’armée américaine. Il fut particulièrement intéressé par les capacités logiques potentielles des ordinateurs et s’inspira grandement des travaux du mathématicien et logicien britannique Alan Turing. Parallèlement à ces recherches, il allait se consacrer à des études mathématiques, telles que la recherche de séquences dans pi, ou logiques, telles que l’étude des automates auto-reproducteurs. Von Neumann allait mourir le 8 Février 1957, des suites d’un cancer probablement dû à des expositions à la radioactivité.

La partie de ses travaux qui nous intéresse ici est son étude des automates auto-reproducteurs. En 1948, von Neumann a proposé un article intitulé « Théorie générale et logique des automates » dans une conférence tenue à Pasadena, en Californie. En 1949, il donna une série de cours sur le thème : « Théorie et organisation des automates complexes ». Une des questions centrales de ce cours était de savoir s’il était possible de concevoir une machine capable de s’auto-reproduire. En effet, il est clair que les objets fabriqués par une machine sont généralement plus simples que la machine elle-même. Prenons l’exemple d’une usine de fabrication de bouteilles de soda, on ne contestera pas dans ce cas que la bouteille est plus simple que la machine qui l’a fabriquée. Même dans le cas d’une usine de fabrication d’ordinateurs, l’outillage utilisé est bien plus complexe que le produit fabriqué.

Von Neumann émit l’idée qu’une machine capable de manipuler des composants de machine élémentaires pourrait résoudre ce problème. Dans sa première conception, l’automate devait puiser dans un réservoir de composants de machine et construire un automate similaire à lui-même, à la façon dont on construit un automate par un jeu de « Meccano ». Mais cela nécessitait que l’automate soit doté d’un système de vision et de reconnaissance suffisamment élaboré pour pouvoir distinguer les différents éléments de machine. Cet automate aurait dû être en outre doté de capacités exceptionnelles pour pouvoir souder et manipuler des tubes à vide sans les abîmer. Ces exigences étaient tout simplement inconcevables étant donné l’état des techniques dans les années 50.

La solution à ce problème vint d’un collègue de von Neumann au laboratoire de Los Alamos : Stanislaw Ulam[7]. Elève de Banach (1892-1945), influencé par les lectures de Sierpinski (1882-1969) ; Ulam est l’auteur d’un problème simple non encore résolu à ce jour : « prenez un nombre, si ce nombre est pair divisez le par 2, s’il est impair multipliez par trois et ajoutez un, vous obtenez une suite de nombres, toute suite finit-elle par converger vers le cycle 4/2/1 quel que soit le terme initial choisi ? » Il est notamment connu pour être l’inventeur de la méthode Monte-Carlo et pour ses travaux sur la fusion nucléaire. Ulam s’intéressait aux « objets géométriques définis de façon récursive »[8] qu’il étudiait après les heures réglementaires de travail en utilisant les ordinateurs du laboratoire de Los Alamos. Ces objets provenaient de jeux aux règles simples dans lesquels on pouvait voir des figures [patterns] se développer, se reproduire, combattre pour une portion de territoire et mourir. Ces jeux se déroulaient dans un univers « cellulaire », composé d’une matrice infinie où les cellules, régulièrement réparties, peuvent être dans un état passif ou un état actif. Les figures de cet univers étaient composées des cellules actives, et à tout moment, le devenir de chaque cellule était dicté par l’état des cellules avoisinantes. Ulam s’aperçut que l’analyse de ces figures défiait le bon sens : elles semblaient évoluer dans un monde qui leur était propre avec des lois bien spécifiques. Il suggéra alors à von Neumann d’utiliser un tel monde abstrait pour pallier les difficultés pratiques qui se posaient pour la construction de l’automate auto-reproducteur. Ce monde serait suffisamment complexe pour pouvoir simuler les opérations élémentaires des machines et en même temps construit de façon à ce que les lois de la physique qui gouvernent ce monde se réduisent à quelques règles simples. L’idée plut à von Neumann qui était habitué à voir les machines comme des circuits logiques[9], il adopta donc l’univers d’Ulam pour commencer à réfléchir à son automate [Poundstone85].

Le problème de l’auto-reproduction

Un premier problème était résolu mais il restait à concevoir un mécanisme d’auto-reproduction. Von Neumann aboutit à l’idée qu’un automate auto-reproducteur devrait comporter une unité baptisée « constructeur universel » qui serait capable de fabriquer n’importe quelle machine (cellulaire) à partir d’une description qui lui serait fournie. Dans le cas particulier où l’on fournirait la description de constructeur universel au constructeur universel lui-même, il y aurait auto-reproduction. Le raisonnement semble simple à première vue mais il se pose un problème de logique : le système auto-reproducteur (SAR) est constitué du constructeur universel (CU) et de sa propre description (DESC). Or cette description ne peut être la description du constructeur universel seulement, elle doit être la description de tout le système, et donc être en particulier une description de la description. En équations, nous avons : SAR = CU + DESC ( SAR ), ce qui paraît a priori insoluble étant donné l’existence d’une régression à l’infini (lorsqu’on remplace SAR dans le terme de droite par le contenu de l’équation).

Ce problème pouvait-il être résolu? Existait-il un moyen d’ « expliquer » à l’automate que la description ne devait pas s’inclure elle-même ? Von Neumann s’inspira des travaux de Turing pour trouver un remède. Nous devons en effet à Church et à Turing l’idée selon laquelle tout calcul [Turing36], et plus généralement tout problème bien formalisé [Turing54] quel que soit sa complexité, peut être réduit à une séquence d’opérations appelée « algorithme ». Ces opérations sont choisies dans un catalogue réduit et leur exécution peut être confiée à une seule machine précise appelée machine universelle. Selon la thèse dite de Church-Turing, cette machine posséderait la capacité (virtuelle) de résoudre tout calcul, aussi complexe soit-il. Nous nommerons cette propriété la « calculabilité universelle[10] ». Le fait que ces opérations élémentaires soient choisies dans un catalogue fini permet leur transcription dans l’univers cellulaire ou le nombre d’états des cellules est aussi fini.

Le problème fut résolu par von Neumann en ajoutant une troisième unité : une machine universelle de Turing, le superviseur, devait orchestrer le processus. L’utilisation du superviseur évitait la régression à l’infinie en distinguant deux phases :

(1) L’ensemble ( constructeur universel + superviseur ), le « copieur-superviseur » réalise une copie de lui-même dans une région vide de l’espace en lisant la description, c’est la phase d’interprétation.

(2) La phase (1) étant terminée, le superviseur comprend qu’il ne faut plus que la description soit interprétée ; celle-ci est considérée comme un ensemble de données et recopiée littéralement pour rebâtir le système initial [Heudin98].

En 1952, la description de l’automate auto-reproductif était terminée et von Neumann proposait une version qui utilise 29 types de cellules différentes. L’état de chaque cellule au temps t était déterminé uniquement par l’état des quatre cellules adjacentes et celui de la cellule centrale au temps t-1. Ce voisinage est d’ailleurs nommé voisinage de von Neumann en hommage à son inventeur. Néanmoins, même dans l’univers simplifié des automates cellulaires, l’ensemble ( constructeur universel + machine de Turing universelle + description du système ) était constitué de plus de 200 000 cellules ! Après cette première « victoire » et de façon assez surprenante, von Neumann allait délaisser l’étude des automates cellulaires pour s’atteler à d’autres problèmes scientifiques et ses résultats concernant l’auto-reproduction ne seront jamais publiés de son vivant. Il est possible que la trop grande complexité de son modèle l’ait déçu. En outre, la « physique » qui régissait ce monde artificiel possédait un défaut majeur : elle n’était pas réaliste puisqu’elle ne respectait pas les conditions de symétrie du monde physique. Cela se traduit mathématiquement par le fait que la fonction de transition f qui règle l’évolution d’une cellule en fonction de son voisinage n’est pas invariante par rotation ou par réflexion (cf. III.1). Par ailleurs, cette trop grande complexité du modèle fit qu’il ne put jamais être testé sur un ordinateur, les capacités de calcul des premiers ordinateurs étant nettement insuffisantes à cette époque.

La première publication sur le sujet provient d’Ulam qui définit alors le concept d’auto-réplication d’une façon formelle [Ulam 50] :

« Un champ d’application intéressant pour des modèles qui sont constitués d’un nombre infini d’éléments interagissant peut être trouvé dans les théories récentes des automates. Un modèle général, considéré par von Neumann et l’auteur, serait comme suit : Etant donné un réseau infini de points, chacun possédant un nombre fini de connections à certains de ses voisins, chaque point a la possibilité de se trouver dans un nombre fini d’états. Les états des voisins au temps t_n induit l’état du point au temps t_n+1. Un des objectifs de la théorie est de prouver l’existence de sous-systèmes qui sont capables de se multiplier, c’est-à-dire de créer dans le temps d’autres systèmes identiques à eux-mêmes. »[11]

Ce n’est qu’en 1966 que la publication du premier grand ouvrage consacré au problème de l’auto-reproduction est enfin réalisée, par Arthur Burks, qui complète les travaux inachevés de von Neumann et publie Theory of self-reproducing automata [vonNeumann66]. Le nom d’ « automate cellulaire » est d’ailleurs une création de Burks. En 1968, le second ouvrage consacré aux AC paraît : il est publié par Codd sous le titre Cellular Automata, sous la forme d’un manuel d’une centaine de pages [Codd68]. Les résultats sont présentés de façon nettement plus concise que dans [vonNeumann66], ce qui va permettre aux étudiants de se familiariser avec le domaine. Les années 60 voient aussi la résolution des premiers problèmes mathématiques liés aux AC. Le problème dit de « synchronisation des fusiliers » a par exemple été inventé par Myhill en 1957, et publié pour la première fois par Moore en 1964 [Moore64]. Il consiste à trouver un automate cellulaire unidimensionnel, tel que, partant d’une configuration où toutes les cellules sont dans l’état de repos (cf. II.1) à l’exception d’une unique cellule, on arrive à une configuration où toutes les cellules sont dans un même état (état dit de ’feu’), état qui n’est jamais apparu avant. Le problème peut s’exprimer de façon imagée comme suit :

« Comment synchroniser une ligne de fusilliers de façon à ce qu’ils se mettent à tirer ensemble, alors que l’ordre donné par un général depuis l’un des deux bords de l’escadron met un certain temps à se propager ? » [Yunes93].

Pour reprendre le vocabulaire de Kuhn dans La structure des révolutions scientifiques [Kuhn70], on peut dire que l’apparition d’un manuel ainsi que la création de problèmes qui occupent une communauté est le signe que ce domaine d’étude devient un champ théorique digne de ce nom, autrement dit qu’un paradigme est en train de naître. Il est néanmoins trop tôt pour dire qu’il existe un nouveau domaine scientifique : les automates cellulaires restent à ce stade une branche particulière ce que les historiens des sciences nomment « la première cybernétique. »

2. Un nouvel axe de recherche : le Jeu de la Vie

Un univers à explorer

Dans le numéro d’Octobre 1970 de Scientific American, Martin Gardner publie un article intitulé « Les combinaisons fantastiques du Jeu de la Vie de John Conway » [Gardner70]. Conway a inventé un automate cellulaire qui a la particularité suivante : des figures peuvent croître et atteindre une grande taille mais pourtant, on ne peut dire de façon évidente s’il existe des figures qui vont croître à l’infini. Cet automate cellulaire se nomme ‘Game of Life’ ou ‘Life’ en abrégé.

Les règles du Jeu de la Vie sont extrêmement simples. Les cellules peuvent se trouver dans deux états qui sont : vivant / mort, l’espace cellulaire est composé de cellules qui se trouvent dans l’état mort au départ, sauf pour un nombre fini d’entre elles. L’évolution de chaque cellule est déterminée en fonction du nombre Nv de cellules vivantes se trouvant dans les huit cases adjacentes à une cellule. Les règles sont :

·                          Une cellule vivante meurt (devient vide) pour Nv = 1 : cela correspond à un état d’isolement de cellule.

·                          Une cellule vivante meurt pour Nv = 4 : cela correspond à un état de surpeuplement autour de la cellule.

·                          Une cellule morte peut devenir vivante pour Nv = 3 : cela correspond à une reproduction « trisexuée ».

Le Jeu de la Vie marque un tournant dans l’étude des automates cellulaires car contrairement aux modèles précédents où l’on décidait des règles et du nombre d’état dans un but bien précis (prouver la calculabilité universelle, la constructibilité universelle), on cherche désormais à trouver les propriétés des automates d’après leur règles de fonctionnement. Le travail des chercheurs s’apparente alors à celui des physiciens qui étudient des phénomènes, préparent des expériences et essaient de découvrir de nouveaux objets. Néanmoins, il existe une différence de taille avec le travail des physiciens : l’évolution des objets manipulés, bien que totalement déterminée par les fonctions de transition, est hautement imprévisible. On remarque ainsi qu’il n’y a pas de correspondance apparente entre la taille d’une configuration initiale et le temps qu’elle met pour se stabiliser. Par ailleurs, le simple fait d’ajouter ou d’enlever une cellule dans une configuration change son évolution de façon radicale. Comment, dans ces conditions, espérer parvenir à construire une expérience ?

 L’étude des propriétés de Life a démarré avec celle de la découverte des objets stables. Généralement, les chercheurs classent les objets selon leur forme de stabilité. Les objets les plus simples à étudier sont ceux qui restent identiques à eux-mêmes avec le temps, un bloc carré de quatre cellules par exemple. Viennent ensuite les objets qui dont l’évolution est périodique, nommés oscillateurs. L’oscillateur le plus simple est le ‘clignotant’ ; il est constitué de trois cellules alignées, et possède une période 2. Une autre classe d’objets importants est celle des objets périodiques qui se translatent avec le temps. Le planeur est l’exemple le plus simple et il apparaît de façon spontanée lors des simulations.

Petit à petit, les chercheurs ont procédé comme des naturalistes et ont découvert des figures stables de plus en plus complexes. Ces découvertes se font selon deux méthodes : la première consiste à initialiser l’espace cellulaire de façon aléatoire et à observer les figures qui apparaissent de façon spontanée (cf. ANNEXE B). La seconde méthode consiste à construire, par des procédés souvent très ingénieux, des figures périodiques qui éventuellement se translatent. Un grand concours -implicite - a débuté au début des années 70 pour la découverte de nouvelles figures stables. Les chercheurs ont rivalisé d’astuce et ont fini par mettre à jour toute une faune exotique qui peuple l’univers du Jeu de la Vie. Des noms aussi évocateurs que « le mangeur, la navette, le crapaud, le phare ou le serpent » ont été donnés (et continuent d’être données) aux figures stables découvertes. On peut dresser un parallèle avec ce qui se produit en astronomie, où les chercheurs rivalisent pour l’observation de nouveaux astres, avec à la clé la possibilité de nommer l’astre du nom du découvreur.[12] Vu de l’extérieur, cette course folle au plus complexe semblait futile aux autres scientifiques. L’étude du Jeu de la Vie prit des proportions telles qu’en 1974, on pouvait lire dans les colonnes du magazine américain Time que « des heures de calcul représentant des millions de dollars avaient été gaspillées par la horde grandissante des fanatiques de ce jeu » [Time74].

Recherche scientifique ou simple passion ?

Ce jugement sévère était-il justifié ? Ces chercheurs étaient-ils des « fanatiques » ou à l’opposé plutôt des « scientifiques » dont la discipline n’était pas encore reconnue ? La recherche des propriétés de Life peut-elle être qualifiée de « scientifique » ? Selon le scénario proposé par Kuhn, une discipline scientifique apporte des « énigmes » [puzzles] à la communauté scientifique concernée. Nous pouvons donc essayer d’estimer la ‘scientificité’ de l’étude du Jeu de la Vie en étudiant les « énigmes » qui sont nées de l’étude du Jeu de la Vie.

Le premier problème fut posé par Conway lui-même qui, en 1970, conjectura qu’il existait des figures (ensembles de cellules vivantes) qui pouvaient croître de façon illimitée. Conway avait créé le Jeu de la Vie en espérant qu’une telle possibilité pourrait être réalisée ; néanmoins aucune preuve mathématique de la réalisation de la croissance illimitée ne pouvait être établie. Il fallait donc exhiber une figure dont l’évolution soit totalement prévisible et dont la taille augmente de façon régulière. Gardner offrit un prix symbolique à celui qui arriverait à prouver ou à réfuter la conjecture de Conway avant la fin de l’année. Le prix fut remporté par William Gosper et cinq autres informaticiens du MIT qui réussirent à exhiber une figure, baptisée lance-planeur (« glider gun »), qui est un oscillateur à l’évolution cyclique et qui a la propriété d’émettre un planeur toute les trente générations. Une telle découverte n’aurait rien d’impressionnant de nos jours mais il faut se souvenir qu’en 1970, nous sommes à l’aube de l’ère informatique et que les simulations d’évolutions se mènent parfois à l’aide de pions de jeu de dames ou d’Othello. L’existence du « lance-planeurs » constituait la première résolution d’une énigme liée au Jeu de la Vie : elle démontrait que la croissance illimitée était possible.

Un autre problème qui a occupé la communauté des chercheurs fut celui de la réversibilité. Un automate est dit être réversible s’il ne se produit pas de perte d’information au cours de l’évolution de l’automate : chaque configuration possède donc un unique successeur (déterminisme de l’AC) et un unique prédécesseur. Il est clair que l’on peut déduire facilement des règles du Jeu de la Vie que l’on n’est pas en présence d’un automate réversible puisque des configurations différentes peuvent avoir un même successeur. Par contre, une propriété qui n’était pas évidente était l’existence de configurations qui n’admettent aucun état qui puisse les engendrer. De telles configurations sont appelées « jardins d’Eden » car elles ne peuvent être que des états initiaux ; on peut donc dire de façon imagée « qu’elles ont tout simplement été crées ». La question du jardin d’Eden est posée pour la première fois par Moore en 1962 [Moore62], concernant les automates auto-reproducteurs. L’existence de jardins d’Eden n’a rien d’évident, car on ne voit pas a priori ce qui empêcherait une configuration donnée d’avoir un prédécesseur. En 1970, le mathématicien Alvy Ray Smith démontra l’existence de jardins d’Eden dans Life, puis un exemple fut donné par Banks. La configuration qu’il propose tient dans un rectangle de 9 par 33 cellules, cf. [Heudin98, p.62], [Poundstone85, p.50], elle est donc relativement complexe ; la démonstration elle-même est assez sophistiquée, ce qui se comprend aisément puisqu’il s’agit de montrer qu’aucune configuration de Life ne peut engendrer le candidat au titre de jardin d’Eden. Le Jeu de la Vie donne donc naissance à des problèmes qui font certes appel à l’informatique mais dont la résolution requiert des techniques purement mathématiques. D’autre part, la découverte de figures stables de plus en plus élaborées semblait montrer que malgré l’impossibilité de prévoir l’évolution de la majorité des configurations, il existait néanmoins un certain ordre dans cet univers.

La calculabilité et la constructibilité universelle dans le Jeu de la Vie

Jusqu’à quel point pouvait-on maîtriser l’univers de Life ? La question fondamentale était de déterminer si Life possédait les capacités de calculabilité et constructibilité universelle. Nous avons vu (cf. I.1.) que Von Neumann avait prouvé qu’un automate cellulaire pouvait servir de calculateur universel en utilisant un modèle qui employait 29 états élémentaires et dont les « lois de la physique » ne respectaient pas les conditions de symétries élémentaires telles que l’invariance par rotation et l’invariance par réflexion. Codd dans [Codd68] a fait un pas de plus vers la simplification en montrant que la condition de calculabilité universelle pouvait être réalisée par un automate cellulaire à 8 états élémentaires avec un voisinage de cinq cellules (4+1) et des règles qui respectaient l’invariance par rotation mais non l’invariance par réflexion. Jusqu’où pouvait-on continuer dans cette recherche de simplicité ? Était-il possible que Life, qui était bien plus simple dans son nombre d’états et dans ses règles puisse avoir la même puissance de calcul et de construction ? Le mystère restera entier jusqu’en 1982 où Conway publiera, avec d’autres chercheurs, une preuve détaillée de la possibilité de simuler n’importe quel calcul à l’aide du Jeu de la Vie [Berlekamp&al.82].

Dans la construction de Conway, l’unité de base qui sert à la circulation de l’information, l’équivalent d’un bit en théorie de l’information, est le planeur. Chaque nombre peut être codé selon un faisceau de planeurs généré par un lance-planeurs, et on montre que toutes les portes logiques telles que ET, OU, NON ainsi que les propriétés de mémoire en lecture / écriture peuvent être réalisées à l’aide d’interactions entre figures stables connues. Conway a aussi montré que l’on pouvait concevoir un constructeur universel dans le Jeu de la Vie. Le lecteur qui souhaiterait avoir un exposé simplifié mais qui reprend chaque étape de la démonstration de Conway peut se reporter à [Poundstone85, chap. 12]. Les constructions utilisées dans la démonstration pourront sembler étranges, complexes, voire tortueuses aux personnes habituées aux mathématiques « classiques », mais si l’on s’y intéresse en détail on retrouve la même élégance, la même quête de l’essentiel que dans une démonstration de mathématiques. Le Jeu de la Vie allait donc apporter la preuve que la condition de calculabilité universelle peut être réalisée par un automate ayant 2 états, un voisinage de 9 cellules, et aux règles invariantes par rotation et par réflexion. A ce jour, des automates cellulaires réalisant la condition de calculabilité et de constructibilité universelle, Life est l’automate le plus simple que l’on connaisse. La démonstration de Conway allait quasiment clore le chapitre concernant le Jeu de la Vie, en effet la possibilité même de la démonstration semblait indiquer que l’on maîtrisait « suffisamment » la physique de ce monde. Il était donc temps d’explorer de nouveaux mondes.

3. L’exploration de l’espace des automates cellulaires

Les recherches se dirigent vers la physique

Parallèlement aux recherches tardives qui se déroulaient sur le Jeu de la Vie, des chercheurs du MIT étudiaient d’autres automates cellulaires ayant des règles simples et qui conduisaient aussi à des comportements imprévisibles. L’un des personnages les plus marquants de cette période fut Edward Fredkin qui eut l’idée d’une règle dite de « compteur de parité » : chaque cellule compte le nombre de ces voisins activés et s’active si ce nombre est impair et se désactive si ce nombre est pair. Le compteur de parité possède une propriété remarquable : toute figure initiale s’auto reproduit en quatre ou huit exemplaires, selon que le voisinage inclut quatre ou huit cellules adjacentes (cf. ANNEXE E). D’autres propriétés doivent être notées : (a) Le temps de reproduction dépend de la taille de la figure initiale et plus une figure est grande et plus le nombre de cycles nécessaires à l’auto-reproduction augmente. (b) Une figure donnée ne peut jamais disparaître avec le temps.

Ce compteur de parité a reçu une application dans l’industrie puisque certains ordinateurs utilisent ces propriétés pour effectuer les tests de mémoire au démarrage. En outre, le compteur de parité de Fredkin apporte un élément important dans la théorie des AC, comme contre-exemple : il est le meilleur exemple d’univers cellulaires où l’auto-reproduction est triviale puisque toute configuration initiale s’auto-reproduit !

Fredkin va former vers 1980 l’Information Mechanics Group au MIT qui inclura des noms qui deviendront célèbres dans le domaine : Tommaso Toffoli et Norman Margolus. Ce groupe de recherche a joué un rôle décisif pour exhiber les potentialités des automates cellulaires dans la résolution et la compréhension de problèmes physiques. A partir de 1984, Toffoli et Margolus ont travaillé à la construction d’ordinateurs spécialement dédiés au calcul parallèle. Leurs travaux ont abouti à la construction d’une machine appelée CAM-6 qui était un proto-ordinateur, en fait un assemblage de puces, destiné à faire tourner des modèles d’automates cellulaires. Cette machine fut perfectionnée et leur nouveau modèle, le CAM-8 fut acquis par des laboratoires américains renommés (Los Alamos, DARPA, Air Force). Toffoli, dans [Toffoli94], signale que le nombre de cellules pouvant être actualisées par seconde grimpe régulièrement et que lorsqu’il atteindra 10¹⁶, le nombre d’Avogadro « en deux dimensions », les simulations seront capables de relier directement le monde microscopique et le monde macroscopique. La direction de recherche initiée par Fredkin, poursuivie par Toffoli et Margolus va se développer en une nouvelle branche dans le domaine des automates cellulaires. Cette branche s’appuie sur la thèse dite de Fredkin qui tient dans la formule lapidaire : « L’univers est un automate cellulaire ». Cette thèse ne doit pas être prise au pied de la lettre mais se veut l’analogue de la thèse de Church-Turing en informatique. Robin Gandy a d’ailleurs proposé une variante de la thèse de Church-Turing qui s’énonce sous la forme «  Tout ce qui peut être calculé par une machine quelconque est effectivement calculable par une machine de Turing[13]» dans un article où il semble prendre la « thèse de Fredkin » (en fait les travaux de von Neumann) comme base de départ [Gandy78]. La « thèse de Fredkin » conduit les chercheurs à privilégier l’utilisation des AC dans la modélisation et la compréhension des problèmes physiques[14]. Nous étudierons plus en détail la portée épistémologique de telles études dans le chapitre III.1.

Les généralisations de Life

L’intérêt pour le Jeu de la Vie n’est pas totalement mort après la démonstration de Conway en 1982. Plus exactement, des chercheurs se sont demandé si les propriétés remarquables du Jeu de la Vie étaient monnaie courante dans l’espace des automates cellulaire ou s’ils résultaient d’un dosage difficile à obtenir. Conway avait consacré deux ans d’expérimentation avant de parvenir à trouver les règles de Life ; était-ce dû au manque de connaissances concernant les AC ou était-ce vraiment difficile de trouver des règles simples qui conduisent à des comportements riches et imprévisibles ?

Des généralisations de Life ont ainsi été proposées et leur étude se poursuit à l’heure actuelle. Le Jeu de la Vie a ainsi été généralisé dans un espace à trois dimensions. D’autre part, des chercheurs ont entrepris la généralisation en changeant les paramètres de Life, en considérant par exemple qu’une cellule morte devenait vivante si Nv (cf . II.1) était compris entre Fb et Fh, qu’une cellule vivante devenait morte si Nv était compris entre en Eb et Eh[15]. Dans cette optique Life est vu comme un point dans un espace fini à quatre dimensions [Heudin97]. D’autres études sont également en cours pour étudier quelles sont les structures stables lorsqu’on augmente le rayon du voisinage de la règle de transition[16]. Des résultats surprenants ont été obtenus, comme l’apparition de glisseurs dont la forme ne change pas alors que les caractéristiques du monde changent (les paramètres Eb/Eh/Fb/Fh). Dans tous les cas, ces recherches tendent à confirmer sous une forme ou sous une autre le fait que Life est un AC qui se trouve dans une « transition de phase », autrement dit dans une zone frontière entre un comportement ordonné et un comportement chaotique. Ce point, qui sera repris plus en détail dans le chapitre II.3., confirme l’idée que la richesse de Life provient d’un réglage particulier, qui ne peut être obtenu qu’après une exploration systématique d’un espace de possibilités bien plus grand. Nous comprenons donc mieux pourquoi il aura fallu près de deux ans d’expérimentation à Conway pour parvenir à construire le Jeu de la Vie.

Le renouveau

L’intérêt pour les automates cellulaires va connaître un regain après la publication d’un article de fond émanant de Stephen Wolfram [Wolfram93]. Wolfram a publié un certain nombre d’articles sur la physique des particules en étant adolescent. Il obtient son doctorat de l’université de Cal Tech en 1980 et rejoint l’Institute for Advanced Study de Princeton en 1982. C’est là, en cherchant des modèles de la façon dont les galaxies s’étaient formées à partir d’un état initial chaotique qu’il s’intéressa aux automates cellulaires. L’originalité du travail de Wolfram tient à ce qu’il est le premier à avoir conduit une étude systématique de la totalité d’un espace d’automates cellulaires. Il a choisi en effet d’étudier les automates cellulaires à une dimension et possédant deux états. Ces automates sont au nombre de 256 (cf. II.1), ce qui rend leur étude systématique possible. Le point fort de la recherche de Wolfram est d’avoir proposé une classification des automates cellulaires en quatre catégories, en s’inspirant de la théorie des systèmes dynamiques. Nous détaillerons dans le chapitre II.3 le contenu de cette classification et les problèmes qu’elle pose.

En 1984, Chris Langton, ancien élève de Burks, relance le débat concernant le travail de von Neumann en remettant en cause la validité de la dichotomie auto-reproduction triviale / non-triviale [Langton84]. Il se base sur le fait qu’il y a peu d’indice en faveur de la thèse selon laquelle les êtres vivants contiennent des systèmes capables de calculabilité universelle. Langton propose alors un schéma d’auto-reproduction qui bien que non triviale selon ses critères, est nettement plus simple que celui de von Neumann. En effet, son automate n’est constitué que de 150 cellules.

En conclusion, l’histoire des AC peut donc être divisée en trois grandes périodes. La première période (1950 à1970) fut principalement tournée vers la résolution du problème de l’auto-reproduction. A bien y regarder, les automates cellulaires ne sont finalement qu’une retombée féconde de ces études et il y a là sans doute une analogie à faire avec les travaux de Turing : la machine de Turing fut elle aussi une retombée féconde des travaux sur l’Entscheidungsproblem (problème de décidabilité des prédicats de l’arithmétique). La seconde période (1970 à 1982) vit le développement des études liées au Jeu de la Vie. A partir du début des années 80, les AC furent étudiés comme classe de modèles et leur intérêt se fit sentir comme moyen de mieux comprendre le monde physique.

Nous pouvons dire qu’à partir du début des années 90, le domaine des automates cellulaires atteint une phase de maturité. Cette maturité se traduit au niveau théorique par l’exploration systématique de grandes classes d’AC comme le font Toffoli, Wolfram et Langton. Au niveau pratique, les automates cellulaires reçoivent des applications dans des domaines aussi variés que la reconnaissance de formes, la cryptographie, l’étude du développement des systèmes urbains [Langlois97], etc. Il semble donc qu’un nouveau paradigme scientifique se soit développé. Ses caractéristiques principales étant de traiter les problèmes selon une approche ascendante (du simple vers le complexe), parallèle et en déterminant les comportement des entités élémentaires de façon locale [Goujon99]. La partie suivante est consacrée à l’étude formelle de ces caractéristiques.

II. LA CONSTRUCTION D’UNE THEORIE

[ Avertissement : sur cette version HTML bon nombre de symboles mathématiques ne sont pas "passés", nous recommandons donc la lecture du fichier original (.doc) ]

A l’aube du XXI^e siècle, l’écriture d’une « théorie des automates cellulaires » est un travail qui reste encore à faire. Pour preuve, il suffit de voir le faible nombre d’ouvrages consacré au sujet, ou l’absence de cours universitaires portant spécifiquement sur le domaine. Ce retard ne peut s’expliquer par la seule jeunesse - relative - du domaine : la théorie dite « du chaos » est  encore plus récente et pourtant le nombre de manuels traitant du sujet est bien plus important. En quoi consisterait donc une « théorie des automates cellulaires » ? Quelles sont les définitions de base d’une telle théorie ? Quels sont les problèmes fondamentaux qui se posent ? Nous avons choisi d’aborder la question en présentant quelques définitions de base qui permettent de saisir ce qui nous paraît essentiel dans la théorie naissante. La présentation se fait d’un point de vue formel, mais ne présente en principe aucune difficulté pour le lecteur familiarisé avec les notations mathématiques. Les lecteurs qui le désireraient peuvent directement passer à la partie III. Nous reprendrons une partie de l’étude faite par Codd dans ce qui peut être considéré comme le premier manuel concernant les automates cellulaires : [Codd68].

1. Définir le paradigme des AC

Définitions de base

            Un automate cellulaire se définit à l’aide de deux types de caractéristiques : structurelles et fonctionnelles. Les premières concernent l’aspect topologique du réseau cellulaire, les secondes concernent l’aspect dynamique de l’évolution du réseau au cours du temps. Le réseau cellulaire peut en effet prendre corps dans des espaces différents, ayant une, deux ou trois dimensions ; l’arrangement des cellules en réseau pouvant aussi être variable (orthogonal, hexagonal). Dans cette partie, nous nous concentrerons sur l’espace cellulaire I x I, qui correspond à un espace bidimensionnel discret et infini, où I est l’ensemble des entiers. Cet espace correspond simplement à un tableau infini rempli de cases carrées, appelées cellules. D’autres espaces peuvent être explorés la seule condition étant que l’ensemble des motifs de base remplissent totalement le plan[17]. La fonction voisinage g est la fonction qui à toute cellule associe l’ensemble des cellules de son voisinage

 g : I x I -> 2^{I x I} ,

g(a) = { a+d1, a+d2,... a+dn }où a ? I x I est une cellule donnée et di ? I x I des translations fixes, où n est le nombre de cellules du voisinage.

Les propriétés fonctionnelles de l’automate cellulaire sont définies par l’automate fini (V,vo,f) qui caractérise le fonctionnement de toutes les cellules du réseau.

·                          V est l’ensemble des états cellulaires

·                          vo un état particulier appelé ’état de repos’,

·                          f est la fonction de transition locale qui à un n-tuple d’éléments de V associe un élément de V.

L’état de cellule évolue à chaque itération, cette itération discrète marque l’évolution temporelle. Nous noterons l’état de la cellule a au temps t par v^t(a), l’état de la cellule au temps t+1 est alors donné par :

v^t+1(a)= f ( v^t(a+d1), v^t(a+d2), ...,v^t(a+dn) )

Ceci exprime simplement le fait que l’état de chaque cellule au temps t+1 est déterminé par l’état des cellules du voisinage au temps t[18]. La fonction f peut être une fonction classique, dans ce cas, on parlera d’automates déterministes ou une fonction faisant intervenir des variables aléatoires, on parlera dans ce cas d’automates probabilistes ou stochastiques [Langlois97]. Dans le cas des automates déterministes, il est essentiel de noter que f est une fonction de Vⁿ dans V, V étant fini, il s’ensuit que l’ensemble des fonctions de transitions s’il est défini de manière extensionnelle, c’est-à-dire à la façon d’un graphe de Vⁿ dans V, est fini. Le cardinal de l’ensemble Vⁿ étant égal à card(V)^n, nous en déduisons que le cardinal de l’ensemble des fonctions de transitions est donc donné par :

card ( {f} ) = card(V) ^ ( card(V) ^ n).

Par exemple, dans le cas des automates cellulaires unidimensionnels, ayant un voisinage de trois cellules (gauche / milieu / droite) et deux états nous avons card(V) = 2 et n=3, d’où :

card ({f})= 2 ^ ( 2 ^ 3) = 2 ^ 8 = 256. L’espace de tous ces automates cellulaires est donc réduit à 256 individus. C’est la taille relativement faible[19] de cet espace qui a permis à Wolfram une étude systématique des automates cellulaires à deux états, trois voisins de dimension 1 [Wolfram93]. Néanmoins, la taille de l’espace des fonctions croît de façon « explosive » avec la taille du voisinage. En passant en deux dimensions, pour n=9, card(V)=2, il vient :

card( {f} ) = 2 ^ (2 ^ 9) = 2 ^ 512 ˜  10^154.[20]

Nous voyons donc qu’il est alors plus fastidieux de spécifier f sous forme de graphe et qu’il est impossible d’entreprendre l’exploration systématique de l’espace des fonctions. De façon pratique, la fonction f se définit à l’aide de règles d’évolution du type « si...alors ». On peut considérer que cette fonction définit les lois de la physique - locales - qui déterminent l’évolution de l’état de cellules à tout instant. Pour continuer l’analogie avec la physique, nous pouvons dire que l’état de vide correspond à ce que nous avons appelé l’état de repos, associé à la propriété de f :

f( vo, vo, vo, ...,vo ) = vo

La mécanique des automates cellulaires est donc entièrement décrite par ces quelques règles. Nous nous apercevons que la physique ainsi définie est une physique ‘super-quantique’ : l’espace est discrétisé, le temps est discrétisé, les états possibles sont discrets et finis, le nombre de règles d’évolution est fini (bien que potentiellement très grand).

Nous avons décrit un espace abstrait qui, bien qu’extrêmement simplifié, doit nous permettre de faire des analogies avec ce que nous observons dans le monde physique. La première de ces analogies est l’identification d’objets, ou comme disent les épistémologues et les spécialistes de sciences cognitives « le processus d’objectivation » : Qu’est-ce qu’un objet ? Par ‘objet’, il faut ici entendre une certaine figure identifiable qui va en quelque sorte mener son existence propre. Pour mieux voir l’apport des AC, nous pouvons faire une comparaison avec l’univers des machines de Turing [Turing36]. Soit la machine suivante :

·                          états : {E1, E2, E3} ; symboles : {X, A} ; état initial : E1

·                          tableau de marche (symbole à écrire, déplacement droite/gauche, nouvel état)

Une telle machine possède la propriété suivante : pour toute suite de A accolés, elle déplace une telle séquence d’une case vers la droite[21]. Un observateur identifiera donc comme objets la séquence de A et verra que de tels objets se déplacent. L’observateur dira : « Tout se passe comme si les séquences de A se déplacent vers la droite ». Maintenant, supposons que nous désirions opérer cela pour toutes les séquences initialement contenues dans le ruban et de façon simultanée. Avec une machine de Turing, cela est impossible : les séquences doivent être déplacées les unes après les autres. Néanmoins, avec un automate cellulaire unidimensionnel, cela est quasi-immédiat. Pour preuve, il suffit de considérer l’automate suivant :

• Si une cellule possède un état X à sa gauche, elle devient X.
• Si une cellule possède un état A à sa gauche, elle devient A.

Les automates cellulaires permettent donc de faire évoluer des objets - qui dépendent du niveau d’analyse où l’on se trouve (cf. III.3) - de la même manière que les objets évoluent dans le monde physique, c’est-à-dire de façon parallèle. Ces objets sont appelés configurations, le paragraphe suivant est consacré à l’étude de ces configurations.

On appellera configuration toute distribution acceptable de l’état des cellules. Une configuration peut donc être représentée par une fonction c : I x I -> V. Une configuration sera dite ‘acceptable’, si l’ensemble des cellules ne se trouvant pas dans l’état de repos est fini. Nous appellerons support de la configuration l’ensemble des cellules qui ne sont pas un état de repos. Formellement, on définit ce support par :

sup(c)= {a ? I x I / c(a) ? vo }

Nous pouvons alors définir la fonction de transition globale F qui a toute configuration initiale c_O, associe les configurations suivantes c₁, c₂, ... c_t, obtenues par répétition de f sur l’ensemble des cellules de l’espace cellulaire . Nous avons :

F(c_t)(a) = f( v^t(a+d1), v^t(a+d2), ...,v^t(a+dn) ) pour tout a de I x I

et

c_t+1= F( c_t)

Il est important de noter que cette fonction n’est pas définie de façon indépendante, mais utilise l’itération de f (fonction locale) sur toutes les cellules de la configuration. Bien que F soit manifestement calculable, il restera à savoir si F est réductible. Autrement dit, un grand problème de la théorie des AC sera de savoir si l’on peut prévoir l’évolution des objets d’un AC sans avoir à effectuer la totalité de la simulation.

Interaction des cellules au sein des configurations

Codd va alors étudier le problème des configurations qui changent avec le temps et de celles qui restent identiques. Il définit pour cela la notion de sous-configuration :

On dira que c’ est sous-configuration de c SSI[22] :

c’ / sup(c’) = c / sup(c’)

c / sup(c’) est la configuration c restreinte au support de la configuration c’( ens. des cellules de c’ qui ne sont pas dans l’état de repos). Une autre définition de la sous configuration est donc :

c’ est donc une sous-configuration de c SSI :

{ a ? sup(c’) => c(a) = c’(a) }.

On dira d’une configuration qu’elle est passive SSI :  F(c) = c

La passivité -simple- d’une configuration traduit sa stabilité par rapport à l’application de F, mais cette stabilité peut provenir des interactions entre les cellules. Aussi est-il nécessaire de définir la notion de passivité complète d’une sous-configuration :

c est complètement passive SSI toute sous-configuration c’ de c est passive.

La notion de passivité complète garantit que la stabilité par rapport à F de la configuration ne provient pas d’interactions entre éléments de F. Le cas limite est celui où la sous-configuration est réduite à une cellule unique : cette cellule doit rester dans le même état par application de F. Par conséquent, nous pouvons noter que les cellules qui composent une configuration totalement passive sont des cellules qui sont incapables de réagir entre elles, donc incapables de transmettre de l’information à elles seules: ces cellules seront en fait utilisées comme support de l’information ultérieurement[23].

La transmission de l’information

Il s’agit maintenant d’étudier la notion de transmission de l’information. Nous commençons par étudier ce qui se passe quand des configurations sont mises les unes à côtés des autres. On dira que deux configurations c et c’ sont disjointes SSI

sup(c) n sup(c’) = Ø

On définit de même l’union de deux configurations disjointes par :

(c U c’) (a)      = c(a)   si a ? sup(c)

                        = c’(a)  si a ? sup(c’)

= vo     sinon

Intéressons-nous maintenant à l’évolution des configurations au cours du temps et notons F^t(c) le résultat de t applications successives de F à la configuration c.

Nous pouvons alors définir la notion centrale suivante relative à la transmission de l’information. Soient c et c’ deux configurations disjointes,

on dira que c passe de l’information à c’ SSI il existe un temps t pour lequel :

F^t( c U c’ ) / Q ? F^t ( c’) / Q                           où   Q= sup( F^t(c’) )

Cette équation traduit l’idée suivante :

c passe de l’information à c’ SSI l’évolution de c’ est perturbée par l’adjonction de la configuration c. Dans cette définition, on ne s’intéresse qu’à un domaine restreint de l’espace : le support du résultat de l’itération de c’. Par conséquent, le test concret de la définition amène à faire deux expériences. Premièrement, on enregistre l’évolution de c’ seule ainsi que l’évolution de son support. Deuxièmement, on enregistre l’évolution de (c’ U c) en se restreignant aux cellules du support précédemment obtenu. On compare à tout instant ces deux enregistrements et s’il y a une différence qui apparaît au temps t, on dira que c’ a passé de l’information à c. Il y a là une analogie à faire avec la définition des contrefactuels en logique modale où l’on peut définir :

P est la cause de Q SSI [ Q ne serait pas arrivé si P ne s’était pas produit ].

Nous verrons dans le chapitre III.3., intitulé Le concept de loi, que ce mode de raisonnement peut permettre de résoudre des problèmes épistémologiques qui se posent lorsqu’on cherche à comprendre ce qu’est une loi (au sens scientifique du terme).

2. La calculabilité et la constructibilité universelle

Dans la partie précédente, nous avons évoqué le fait que les automates cellulaires ont la même puissance de calcul que les machines de Turing. Nous allons maintenant étudier cette propriété de calculabilité d’un point de vue formel et nous intéresser aux définitions mathématiques qui sont nécessaires pour exprimer la propriété de calculabilité. Il est clair que certains automates cellulaires possèdent la capacité de calcul universel et que d’autres en sont dépourvus[24]. Les questions posées au sujet de la calculabilité se traitent en termes similaires pour les machines de Turing et pour les automates cellulaires. Ceci ne doit pas nous surprendre car un automate cellulaire réagit de la même façon qu’une machine de Turing, la différence fondamentale étant que toutes les cellules de l’espace cellulaire peuvent être actives et changer d’état, alors que dans une machine de Turing (M.T), seule la tête de lecture possède la capacité de changer l’état d’une cellule. En revanche, nous verrons que les automates cellulaires enrichissent le domaine d’étude des M.T en posant la question de la constructibilité universelle. Qualitativement, cette question se pose en ces termes : Est-il possible de concevoir un ‘constructeur’ tel que, si l’on lui ‘donne’ une description complète d’une configuration à obtenir, cette configuration soit ‘construite’ en un nombre fini d’étapes ?

La calculabilité

Il a déjà été prouvé de façon constructive que divers modes de calcul réalisent la condition de calculabilité universelle [Odifreddi89], citons par exemple :

·        les définitions de fonctions par machines de Turing,

·        la récursivité générale,

·        le lambda-calcul,

·        les définitions de fonctions par système formel[25],

·        les systèmes de réécriture de Post.

Von Neumann, puis Codd ont élargi cette liste en prouvant de façon constructive l’équivalence de la puissance de calcul des machines de Turing [Turing36] et des automates cellulaires. Le choix des machines de Turing est assez naturel : dans une telle machine les informations sont stockées sur un ruban subdivisé en cases ; il y a donc une certaine « proximité » avec le modèle des AC. Il est clair que le principal obstacle à l’établissement de la démonstration d’équivalence provient de ce que le fonctionnement des automates cellulaires est parallèle alors que celui des machines de Turing est séquentiel. Une machine de Turing permet en effet de suivre l’évolution de la machine et de son ruban pas par pas, à chaque étape seule une case du ruban peut être modifiée. Dans l’univers des AC, il n’est pas directement possible de suivre les modifications puisque à chaque étape toutes les cellules ont la capacité changer d’état. Pour montrer qu’à toute machine de Turing peut être associée un automate cellulaire équivalent, il va donc nous falloir « désactiver » le parallélisme. Ceci ne présente pas d’obstacle majeur mais conduit, si l’on s’y prend de façon « brutale », à utiliser un grand nombre d’états différents, limitant par-là l’intérêt d’utiliser des AC comme modèle. On comprend dès lors la difficulté à prouver de façon constructive l’existence d’un calculateur universel qui n’utilise qu’un nombre restreint d’états : 29 pour von Neumann, 8 pour Codd. Ces deux démonstrations sont assez longues, la construction de von Neumann [vonNeumann66] étant difficilement compréhensible dans sa totalité, celle de Codd étant plus accessible [Codd68]. Nous ne chercherons pas ici à expliquer comment on peut effectivement construire une machine dotée de la capacité de calculabilité universelle dans un univers cellulaire et nous recommandons au lecteur intéressé de se reporter à [Codd68] ; par contre, nous pouvons concentrer notre attention sur les définitions fondamentales qui précèdent la démonstration. Ces définitions sont en effet les briques élémentaires qui vont permettre que le domaine, nouveau pour l’époque, des automates cellulaires gagne le statut de domaine autonome. Pour reprendre la terminologie de Kuhn, on dira que ces définitions sont l’acte de naissance d’un nouveau paradigme [Kuhn70].

Nous considérons une machine de Turing T qui opère sur une bande bi-dimensionnelle, ceci pour faciliter la correspondance entre les deux modèles. Soit T l’ensemble des bandes qui contiennent seulement un nombre fini de symboles non vides et W l’ensemble des symboles utilisés dans T. Une fonction partielle ? est dite calculable par machine de Turing, s’il existe une machine de Turing munie de l’alphabet W qui calcule ?.

La première étape dans la démonstration de l’équivalence M.T / A.C consiste à associer l’espace des bandes T à l’espace cellulaire Z muni de configurations totalement passives. Nous retrouvons là le fait que les cellules des configurations totalement passives sont de simples supports de l’information.

On dira alors que la fonction ? est calculable dans Z SSI il existe :

une configuration c, une cellule a ? sup(c) et un état v différent de l’état de repos - qui correspond à l’état d’arrêt de la M.T - , tels que :

pour toute configuration d ? T, il existe un temps t pour lequel :

(A)                     Ft( c U d) / sup(T) = ?(d) avec sup(T)= U sup(d), d ? T

(B)                     Ft(c U d)(a) = v

(C)                     Ft’(c U d)(a) ? v, pour tout t’< t.

Cette définition peut sembler à première vue assez compliquée. Analysons donc la signification des conditions (A), (B) et (C) à l’aide du tableau suivant :

Il apparaît alors que :

(A)  signifie que ?(d) a effectivement été calculée,

(B)   signifie que l’état de fin de calcul a été atteint au temps t,

(C)  signifie que l’état de fin de calcul n’a jamais été atteint avant le temps t.

Codd peut alors définir deux concepts dérivés du concept de calculabilité pour les AC. Nous commençons par définir la translation de configuration :

On dira que s’ est une translation de la configuration s SSI il existe un élément d ? I x I tel que

s’(a) = s( a + d) pour tout a ? I x I , qu’on notera s’= s_d en abrégé.

On dira d’un espace cellulaire qu’il possède la propriété de calculabilité universelle si pour toute fonction calculable par M.T ?, il existe une configuration c qui calcule ?, au sens défini précédemment. S’il existe une configuration c telle que :

 pour toute fonction calculable par M.T ?, il existe une bande d ? T et une translation d telle que d_d est disjointe de T et de c , et telle que c U d_d calcule ?,

alors cette configuration c sera qualifiée de calculateur universel.

Nous venons de définir l’équivalent de la machine de Turing universelle dans le domaine des automates cellulaires[26]. Nous verrons dans les chapitres qui suivent que cette notion se place cœur d’une épistémologie des automates cellulaires.

La constructibilité

Nous pouvons désormais utiliser la spécificité des automates cellulaires pour enrichir notre capital de définitions : il s’agit de définir la propriété de constructibilité. Une configuration donnée peut en effet évoluer en conduisant à la création d’autres configurations, lesquelles configurations vont à leur tour pouvoir évoluer librement dans l’espace cellulaire. Si on fait l’analogie « configuration = objet » la notion de constructibilité devient proche du concept de production. Il devient possible de poser des questions telles que : « A quelle condition un objet X peut-il être produit par un objet Y ? ». Codd propose de formaliser cette question comme suit :

c et c’ étant deux configurations, on dira que c construit c’ SSI il existe un temps t pour lequel :

·        c’ est une sous-configuration de F^t(c) disjointe de c

·        ( F^t(c) - c’ ) ne passe pas d’information à c’.

En clair, la configuration construite (l’objet construit) doit être construite à l’extérieur de la configuration initiale(le constructeur). Par ailleurs, une fois terminée l’étape de construction de l’objet construit, il ne doit y avoir aucune interaction entre le constructeur c et l’objet construit c’ : l’évolution de c’ doit se faire identiquement selon que c est présente ou non. Cette contrainte est une contrainte très forte, qui élimine de nombreux cas d’auto-reproduction triviale. Ceci correspond bien à l’idée que nous nous faisons d’une machine-outil : celle-ci conduit à l’élaboration d’autres objets (éventuellement des constituants de machines-outil) qui deviennent alors indépendants de la machine qui les a créés.

La propriété de construction universelle requiert qu’un espace cellulaire puisse accueillir un ensemble de configurations C qui calcule toute fonction calculable par machine de Turing. On dira que C est un ensemble complet de calculateurs s’il existe une configuration c_u tel que toute configuration c de C puisse être construite par adjonction de configurations disjointes de C, alors c_u est appelé un constructeur universel et l’espace accueillant c_u est dit posséder la propriété de constructibilité universelle[27].

Nous approchons du problème central de l’auto-reproduction, tel que von Neumann l’a posé, à savoir un automate peut-il construire un autre automate, et particulièrement peut-il construire un automate similaire à lui-même ? La propriété essentielle d’auto-reproduction qui se définit comme suit :

c est dite être auto-reproductive s’il existe une translation d telle que c construit c_d

 (la configuration c translatée de d).

Nous sommes désormais équipés pour distinguer l’auto-reproduction triviale de l’auto-reproduction non-triviale, selon la définition de von Neumann[28]. Nous dirons ainsi qu’une configuration c réalise la condition d’auto-reproduction non triviale si c est auto-reproductive et si c est un calculateur-constructeur universel. Nous verrons dans le chapitre III.2 que la distinction entre auto-reproduction triviale et non-triviale est fondamentale, et conduit à s’interroger sur la définition même de la vie.

Ces définitions, héritées en partie du monde de la logique (notion de calculabilité universelle) sont le point de départ d’une réflexion que l’on peut qualifier de ‘technique’ et qui vise à la construction effective d’un ‘ordinateur’ dans le monde cellulaire et d’une machine auto-reproductrice. A ce jour, seuls trois types d’automates auto-reproducteurs non triviaux (au sens défini précédemment) ont pu être effectivement construit dans un espace cellulaire bidimensionnel : il s’agit de l’automate de von Neumann, celui de Codd et de Life. Dans les deux premiers cas, l’espace cellulaire a été construit dans le but spécifique d’accueillir une configuration auto-reproductrice (non triviale) ; dans le cas de Life, il a fallu près de douze ans de recherches (1970-1982) pour parvenir à exhiber une telle configuration. La propriété de calculabilité-constructibilité universelle est donc un joyau rare dans le monde des automates cellulaires et la preuve de l’existence de cette propriété pour un automate donné reste le fruit d’un travail de longue haleine.

3. Problèmes fondamentaux de la théorie des AC

Le domaine des AC a été une source de nombreux problèmes logiques et mathématiques. Nous avons mentionné l’auto-reproduction, la synchronisation d’une ligne de fusilliers, l’étude des figures stables du Jeu de la Vie, l’existence d’un « jardin d’Eden » ; pour ne citer que les problèmes les plus célèbres. Nous allons ici nous intéresser à un problème qui reste ouvert : celui de la classification des automates cellulaires. Nous verrons quelles sont les difficultés qui se posent dans ce problème et les études auxquels il conduit.

La classification des AC

Nous avons vu (cf. I.3 & II.1) que l’article [Wolfram83] a relancé l’intérêt des chercheurs pour les automates cellulaires. A partir de l’étude systématique des automates cellulaires unidimensionnels à deux états, Wolfram a proposé une première classification des automates cellulaires selon leur comportement dynamique. Cette classification comporte quatre classes. Les trois premières sont inspirées des catégories qui apparaissent dans l’étude des systèmes dynamiques, la quatrième étant la plus intéressante puisque spécifique au domaine des AC.

Le problème de cette classification est que la classe d’un automate ne peut être déterminée qu’a posteriori, c’est-à-dire par simulation et observation du comportement. Ceci implique que la classification n’apportera d’information que dans la mesure où elle peut être reliée aux caractéristiques fonctionnelles (e.g. la complexité des règles de transition) de l’automate cellulaire. Nous pouvons donc dire que cette classification, loin d’apporter une réponse définitive à la caractérisation de la dynamique des automates cellulaires, donne au contraire naissance à un certain nombre de questions ; la question primordiale étant : « Comment prévoir la classe d’un automate cellulaire au seul vu de sa fonction de transition ? »

Par ailleurs, nous pouvons noter que les frontières entre les différentes classes sont définies de façon qualitative[29]. Comment, par exemple, savoir si l’on est en présence d’un automate de classe IV ou de classe III ? Jusqu’à présent, c’est généralement en observant le comportement des automates et en décidant « à vue d’oeil » que les chercheurs ont classé les automates. Il n’existe pas à ce jour d’algorithme qui tranche entre les classes. Wolfram a émis l’hypothèse qu’une propriété des automates de la classe IV est de réaliser la calculabilité universelle. Dans ce cas, des résultats d’indécidabilité ont été obtenus : il serait alors impossible d’arriver à trouver une méthode systématique pour décider de la classe d’un AC [Culik88]. La pertinence de cette classification a donc été largement discutée dans la communauté des chercheurs qui travaillent sur les AC. De nombreuses autres propositions ont depuis été émises, néanmoins aucune d’entre elles ne s’est imposée de façon définitive et le problème de la classification des automates cellulaires reste posé à ce jour.

L’hypothèse de Langton

En 1991, Langton a proposé une première possibilité pour relier un paramètre des automates cellulaires à leur classe [Langton90]. Remarquant que dans les systèmes physiques, il existe généralement un paramètre que l’on peut faire varier continûment pour passer d’un système d’un comportement régulier à un comportement chaotique, il essaya de trouver un équivalent pour les automates cellulaires. Il aboutit au choix du paramètre lambda qui est la fraction d’états qui d’après les règles de transition, conduisent à activer une cellule dans la prochaine génération. Soit, formellement :

lambda = card { X ? Vⁿ / f( X ) ? vo} / card { Vⁿ },

en reprenant les notations précédentes (rappel : vo = état de repos, V = ens. des états possibles, f = fonction de transition, card = cardinal d’un ensemble).

Les résultats des expérimentations ont montré que l’évolution de la dynamique des automates cellulaires suivait l’évolution de lambda selon le tableau suivant :

Ces recherches, effectuées pour des AC unidimensionnels semblent donc montrer qu’il existe une « transition de phase » liée au paramètre lambda. Néanmoins, l’utilisation de ce paramètre comme outil de prévision de la dynamique ne fait pas l’unanimité. Langton lui-même a admis que la thèse qu’il a émise n’était pas toujours en adéquation avec les résultats observés. Les études des généralisations du Jeu de la Vie, semblent même démontrer que l’utilisation de lambda comme paramètre de prévision donne des résultats contraires à ceux qu’on observe. Les études qui ont montré l’inadéquation de lambda ont conduit soit à chercher un meilleur paramètre, soit à proposer une classification différente de celle de Wolfram. Jean-Claude Heudin propose ainsi de prendre en compte deux paramètres pour caractériser la dynamique des AC : la croissance et la périodicité [Heudin97].

Si la pertinence du paramètre proprement dit est discutable, les travaux de Langton ont conduit à émettre une thèse dont la portée philosophique est bien plus générale : la vie, symbolisée par la classe IV (cf. III.2.), serait un phénomène susceptible de se trouver en l’ordre, symbolisé par la classe II et le chaos, symbolisé par la classe III. Pour généraliser encore, il semblerait que l’émergence de la vie dans l’univers ne soit possible que grâce à un ajustement exceptionnel des lois fondamentales de cet univers, le plaçant à la frontière entre l’ordre et le chaos.

            Ce rapide tour d’horizon théorique nous a permis de découvrir quelques traits caractéristiques du paradigme des AC, à savoir :

• L’espace qui accueille les objets est par essence discret, il est constitué d’entités élémentaires, indivisibles, pouvant avoir un nombre fini d’états : les cellules. Le temps s’écoule de même de façon discrète.
• Les objets de cet univers sont des ensembles de cellules qui ne se trouvent pas dans l’état de repos : ce sont des configurations.
• Les lois de la physique qui règlent le comportement de ces objets sont et de nature locale et microscopique : elles ne décrivent pas le comportement de l’objet en totalité mais dictent, de façon déterministe ou stochastique, le comportement de chaque cellule.
• La notion d’information est primordiale. Certains AC peuvent réaliser les conditions de calculabilité et de constructibilité universelle.

III. LES ENJEUX EPISTEMOLOGIQUES

La partie précédente était consacrée aux énigmes spécifiques au domaine des AC. Dans le cadre d’un mémoire d’histoire et de philosophie des sciences, nous allons pouvoir nous « évader » de la stricte théorie des AC et voir comment les recherches dans ce domaine ont conduit les scientifiques à formuler des interrogations d’ordre philosophique. Ne prétendant pas à l’exhaustivité, nous avons sélectionné quelques questions qui touchent à trois domaines : la physique, la biologie et la compréhension du concept de « complexité ».

1. Au cœur de la physique

La question de la symétrie

            Jusqu’à présent les AC n’ont été étudiés que du point de vue de la logique et de l’informatique. On peut se demander si leur intérêt se limite à ces seules sciences ou s’ils peuvent aussi servir à la résolution des problèmes physiques. Tommaso Toffoli, de l’Information Mechanics Group (cf. I.3) fait remarquer que le modèle de von Neumann est basé sur des pures considérations logiques et que les règles de transition de son automate cellulaire ont un aspect purement ad hoc :

« Son modèle n’essaie pas d’appréhender les mécanismes physiques et chimiques sous-jacents, mais utilise des règles complexes qui imitent directement les aspects de la phénoménologie d’agrégats macroscopiques. »[30][Toffoli94].

En effet, on peut légitimement critiquer les règles de transition décidées par von Neumann, notamment en leur reprochant de ne pas respecter les conditions de symétrie spatiales telles que l’invariance par rotation et par réflexion. Codd écrit ainsi :

« Nous noterons au passage que l’espace de von Neumann à 29 états et 5 voisins est invariant par rotation mais pas au sens fort [au sens classique des physiciens]. C’est une chose curieuse sachant que von Neumann accordait une grande importance à l’isotropie. »[31] [Codd68, p.16]

Par contraste, les lois élémentaires de la physique respectent toutes l’invariance par symétrie[32] axiale et par rotation ; aussi est-il naturel d’attendre d’un modèle d’automate cellulaire qu’il respecte ces invariances.

A notre tour nous pouvons critiquer le modèle de Codd en faisant remarquer « au passage » que le modèle proposé par Codd est invariant par rotation mais pas par réflexion. Analysons pourquoi cela peut être gênant à partir d’un exemple. Dans le modèle de Codd - comme dans celui de von Neumann - le constructeur universel opère à l’aide d’un bras constructeur. Les signaux qui dirigent ce bras sont guidés à l’aide d’une gaine de cellules inertes (symbolisés par l’état 2) et l’ensemble gaine + signaux constitue un bras constructeur. La figure ci-dessous montre par exemple la propagation du signal 07 dans une telle gaine.

temps t:                                         t+1:

2 2 2 2 2 2 2 2 2 2 2 2 2            2 2 2 2 2 2 2 2 2 2 2 2 2

1 1 1 0 7 1 1 1 1 1 1 1 1     ->     1 1 1 1 0 7 1 1 1 1 1 1 1

2 2 2 2 2 2 2 2 2 2 2 2 2            2 2 2 2 2 2 2 2 2 2 2 2 2

On peut imaginer que le signal 07 aura pour effet de faire croître la longueur du bras d’une unité, cela ne pose pas de problèmes conceptuels. En revanche comment faire si l’on veut faire tourner la gaine de 90 degrés vers la droite ? La symétrie horizontale de la figure impose que quel que soit le signal injecté, celui-ci n’ait pas plus de raison d’agir sur la droite du bras que sur la gauche de celui-ci. Dans le modèle de Codd, il y a la décision ad hoc que le signal 04 fera tourner le bras vers la gauche et que le signal 05 fera tourner le bras vers la droite[33]. Cela est embêtant si nous supposons que les AC sont sensés modéliser des « opérations minimales » (cf. I.1). Notons que les conditions de symétrie que l’on souhaiterait avoir n’imposent nullement l’impossibilité de faire tourner le bras spécifiquement à droite, elles imposent seulement que le signal qui soit responsable de la rotation à droite ne soit pas symétrique lui-même. Par exemple on pourrait imaginer que :

10

17        ait pour effet de faire tourner le bras à droite, alors que :

17

10        ait pour effet de faire tourner le bras à gauche.

On comprend donc la pertinence de la remarque de Toffoli (citée ci-dessus) : les phénomènes observés dans les modèles de von Neumann ou de Codd ne sont pas impossibles, ils constituent de sérieux « raccourcis » par rapport à ce qui se produit dans un univers physique et ne peuvent donc en aucun cas représenter des processus élémentaires. Sa sévérité envers la construction de von Neumann est sans nuance:

« On pourrait dire que le modèle de von Neumann est un modèle de la “vie” seulement dans la même mesure où le jeu d’échec est un modèle de la « guerre » : un jeu de plateau qui ne capture que de façon qualitative des boucles de rétroaction majeures qui existent dans certaines situations particulières. Je suis convaincu que les raccourcis même qui ont conduit à rendre le projet de von Neumann réalisable ont en partie mené les automates cellulaires dans une impasse, et ce pour deux ou trois décennies. »[34] [Toffoli94]

Cet argument peut être tempéré si l’on considère que calculabilité et constructibilité universelles ont pu être prouvées (par construction) dans Life, qui est un automate dont les règles de transition respectent la symétrie par rotation et par réflexion. Il est vrai que là encore, des difficultés surgissent si l’on veut analyser l’adéquation avec le monde physique : Life ne permet pas de modéliser une loi aussi élémentaire que celle de la conservation de la matière[35]. Plus généralement, dans un modèle classique d’AC, il est impossible de « suivre » une particule à la trace. Si l’on identifie une particule de matière avec une cellule qui n’est pas dans l’état de repos, on observe que la matière apparaît et disparaît spontanément. Il y a là un point important à souligner : en règle générale, les cellules d’un automate cellulaire ne doivent pas être identifiées à des éléments de matière mais à de l’information. Par exemple, dans le cas de l’automate auto-reproducteur, lorsque le bras constructeur « grandit » d’une cellule (abstraite), deux interprétations s’offrent à nous :

Selon l’interprétation classique, on dit que le bras s’est allongé d’une cellule par création d’une nouvelle cellule, par bourgeonnement par exemple. Selon l’interprétation en terme d’information, on dira que le bout du bras a changé d’état et que ce changement d’état a conduit le bras à grandir. Dans l’interprétation « cellule = matière », on passe sous silence le problème de l’apport des nutriments à la cellule et on suppose que de la matière peut être créée ex-nihilo. Dans l’interprétation en terme d’information, on dira simplement qu’une structure porteuse d’un certain ordre s’est auto-reproduite, sans faire la moindre référence au support de la structure et en ne posant donc pas le problème de l’apport de matière.

Les chercheurs n’ont pas pour autant renoncé à identifier chaque cellule active à une particule de matière. Ceci a conduit à proposer des modifications du modèle classique d’automates cellulaires. Dès 1976, des modèles d’AC qui permettent de modéliser la conservation de la matière ont été élaborés. La première proposition, connue sous le nom de modèle HPP (cf. schéma en ANNEXE A), du nom des inventeurs, a été d’appliquer la règle de transition non plus pour changer l’état d’une cellule, mais par blocs de 2 x 2 de cellules (voisinage de Margolus).

Ce changement, même mineur, dans le paradigme classique des AC, nous fait sentir que, comme toute classe de modèles, leur utilisation possède des limites. Dans leur conception classique, ils sont adaptés à la modélisation des flux d’information. Pour leur faire jouer le rôle d’outil de modélisation de flux de matière ou d’individus, il faut nécessairement procéder à des modifications du modèle de base, par exemple en utilisant la technique de mise à jour par blocs, dans laquelle la règle de transition ne s’applique pas à une cellule mais à des groupes de cellules[36].

Si nous voulons estimer dans quelle mesure ces limites définissent un nouvel horizon dans notre façon de connaître le monde, il peut être utile d’aller consulter la philosophie de Kant. Si nous nous rapportons à la table des catégories de la Critique de la Raison Pure, Analytique des concepts [Kant], nous avons trois catégories de la relation qui permettent la constitution de l’expérience:

(a)    Inhérence et subsistance (substancia et accidens).

(b)   Causalité et dépendance (cause et effet).

(c)    Communauté (action réciproque entre l’agent et le patient).

Or, dans l’univers des AC, la seule catégorie immédiatement donnée est (b)[37]. Il y a là une différence fondamentale avec l’univers de la physique[38] où les trois catégories apparaissent généralement (de façon explicite ou non[39]). C’est justement le rôle du chercheur que de chercher les conditions dans lesquelles on peut faire apparaître des objets qui se plient à ses catégories. L’utilisation du glisseur dans Life en est le meilleur exemple : le glisseur est une configuration dont la forme et la taille (la substance) reste identique[40] au cours du temps (catégorie (a)), et qui permet d’interagir avec d’autres formes telles que le bloc ou les autres glisseurs (catégorie (c)). Une telle étude mérite certainement un examen plus approfondi ; dans le cadre de ce mémoire, nous pouvons simplement retenir que les objets qui apparaissent dans l’univers des AC ne se prêtent pas spontanément à l’étude et à la manipulation, et que le chercheur a un rôle prépondérant pour parvenir à la maîtrise de ces objets.

Étude d’un exemple  : le modèle d’Ising.

Nous allons maintenant examiner un exemple simple - et réussi - d’automate cellulaire modélisant des phénomènes physiques. Un aimant possède la propriété de perdre son aimantation s’il est chauffé au-dessus d’une certaine température, appelée température de Curie (Tc) et reprend son aimantation lorsqu’il est refroidi[41]. Pour expliquer ce phénomène, on peut considérer que le matériau ferromagnétique est constitué d’un réseau régulier de domaines (spins) qui peuvent avoir deux orientations haut et bas. On modélise alors les interactions entre spins sous la forme suivante : un spin change son orientation en fonction de l’orientation des spins voisins, adoptant de préférence une configuration semblable à celle de ses voisins. La probabilité de changement d’orientation est contrôlée par une variable aléatoire. On peut alors faire l’analogie suivante : le changement d’orientation correspond à minimiser l’énergie (localement) et le contrôle de la probabilité est équivalent à la température, facteur d’introduction de « désordre » [Galam98, Toffoli94].

La simulation montre que partant d’une configuration aléatoire, plusieurs comportements sont possibles. Pour T>Tc, la configuration reste aléatoire. Pour T<Tc, on s’aperçoit que des groupes se forment petit à petit jusqu’à ce qu’on distingue clairement deux phases séparées. Le bruit thermique permet aux phases d’évoluer jusqu’à ce que l’une d’elles finisse par dominer tout le plan. On peut même simplifier encore le modèle d’Ising en un modèle dit ‘du vote de majorité’. La règle de transition se définit comme suit :

·        Chaque cellule compte le nombre de cellules dans l’état haut et bas dans les huit cases voisines.

·        Si le nombre de voisins dans l’état haut (resp. bas) est supérieur au nombre de cellules dans l’état bas (resp.haut), la cellule prend l’état haut (resp. bas).

·        Si le nombre est égal, la cellule conserve son état.

Pour ce modèle, on observe de même une séparation des phases et une convergence très rapide vers un état d’équilibre (cf. ANNEXE C). De même que pour le modèle d’Ising, l’introduction de bruit permet aux phases d’évoluer jusqu’à ce que l’une des phases recouvre tout le plan.

Nous avons ici choisi un exemple qui nous paraît représentatif de la puissance des AC comme outil de modélisation. Les exemples d’utilisation d’automates cellulaires pour la modélisation de phénomènes physiques sont trop nombreux pour pouvoir être énumérés. Citons comme second exemple la modélisation des milieux dits « excitables ». Ces modèles sont utilisés pour l’étude des réactions chimiques oscillantes[42], pour simuler la propagation des feux de forêt (cf. ANNEXE D), ou pour simuler les opérations de réaction-diffusion [Turing52] qu’on retrouve à l’origine des formes des rayures sur les animaux. Le lecteur désireux d’en savoir plus pourra se reporter à l’excellent ouvrage de Philip Ball, The Self-Made Tapestry [Ball98]. Dans tous les cas, l’essentiel est que les modèles qu’utilisent les physiciens font tous apparaître des propriétés macroscopiques, telles que la température, la courbure des frontières entre phases et leur tension de surface à partir de la spécification, non pas d’équations, mais de règles microscopiques simples.

La relation discret / continu au cœur d’une épistémologie de la modélisation.

Depuis la montée en force de la puissance de calcul des ordinateurs, une grande partie de l’activité scientifique, qu’il s’agisse du domaine de l’ingénierie ou celui de la recherche est basée sur la modélisation et la simulation. Par modélisation on entend la description d’un phénomène dans un langage compréhensible par les machines, à l’aide d’équations ou d’algorithmes ; la simulation est l’opération de calcul proprement dite. Nous allons ici nous focaliser sur les modélisations qui partent du comportement d’entités microscopiques et qui arrivent à prédire (avec justesse ou non) la valeur de paramètres macroscopiques . Les entités microscopiques dont nous parlons peuvent être des atomes, des grains de sable, des voitures ou n’importe quel objet du système dont on pense connaître le comportement sans avoir à le décomposer en sous-parties. Qu’est-ce qu’une donnée macroscopique ? Il s’agit d’un paramètre obtenu par un calcul statistique, une moyenne par exemple, sur un grand nombre d’individus. La pression, la densité ou la température sont des exemples de ces paramètres macroscopiques, qui n’ont aucune signification lorsqu’on examine une particule donnée.

Un autre paramètre tient un rôle majeur en physique (en thermodynamique plus particulièrement), il s’agit de l’entropie. L’entropie est une mesure de la « qualité » d’une énergie, de sa disposition à fournir du travail. Plus l’entropie d’un système augmente et moins celui-ci se trouve disposé à servir comme source de travail. Le second principe de la thermodynamique stipule que pour tout système isolé, l’entropie ne peut qu’augmenter ou rester égale. Cela explique par exemple pourquoi il est impossible à un bateau d’avancer en puisant l’énergie de l’eau et en laissant une traînée de glace derrière lui, un tel phénomène ferait diminuer l’entropie globale et violerait le second principe. Des travaux de Boltzmann en mécanique statistique, nous savons que l’entropie peut être calculée en comptant le nombre d’états microscopiques qui sont compatibles avec un état macroscopique donné.

Le modèle d’Ising ainsi que le modèle du ‘vote de majorité’ nous ont montré que des propriétés macroscopiques émergeaient des lois élémentaires. Toffoli nous dit qu’en analysant le modèle de vote de majorité, nous voyons apparaître une règle de correspondance qui serait « le phénomène de tension de surface est la manifestation universelle, au niveau microscopique, de la loi du ‘vote de majorité’ au niveau microscopique. » Plus généralement, il défend la thèse que les automates cellulaires permettent la compréhension des principes de base de la physique. Cette thèse se base sur les deux principes suivants :

1. Des phénomènes dont le comportement ont un aspect continu émergent, à un niveau macroscopique de presque tout mécanisme microscopique discret.
2. Presque toutes les équations différentielles de la physique que l’on connaît peuvent être considérées comme des comportements limites de mécanismes microscopiques discrets.

Pour expliquer sa thèse, Toffoli va se placer un espace d’automates cellulaires possibles dont le format est fixé, c’est-à-dire dont la matrice, le voisinage, le nombre de bits par états est fixé, et dont les règles de transition varient. Prenons, dit-il, une page d’un journal et codons-la comme configuration initiale de l’automate cellulaire[43]. Comment évolue la configuration ? Très probablement, après une génération seulement, toutes les régions seront quasiment grises et l’image aura presque disparu. Après quelques générations, l’image sera complètement grise et ne contiendra plus aucune information, l’entropie sera maximale. Ce comportement n’est pas obtenu systématiquement, bien entendu, mais en explorant l’espace quasi-infini des règles possibles, nous constatons que la fraction des automates « intéressants » (ceux qui ne maximisent pas l’entropie au bout de quelques générations) sur la fraction des autres automates tend vers 0. Pour reprendre l’expression mathématique consacrée, on dira que l’espace des automates non triviaux est de mesure nulle. Une conséquence est donc la confirmation partielle de la règle 1 de la thèse de Toffoli, la majorité des AC exhibent bien un comportement macroscopique, en l’occurrence la maximisation de l’entropie.

Nous pouvons alors concentrer notre attention sur un espace de règles de transition plus intéressant: celles qui conservent le nombre de particules[44]. Ce faisant, nous évitons de tomber dans les cas triviaux précédents et nous voyons qu’une dynamique apparaît au niveau macroscopique : cette dynamique est réglée par l’équation de diffusion qui s’exprime par : d? / dt = k.?²?. Toffoli en conclut qu’il existe une « classe d’équivalence » entre l’équation de diffusion et les règles de transition qui conservent le nombre de particules. De même, le modèle HPP décrit précédemment conduit à des dynamiques macroscopiques représentées par l’équation de Navier-Stokes, utilisée en mécanique des fluides pour le calcul des écoulements.[45]

Bien sûr, les exemples donnés ne constituent pas une démonstration, mais nous sommes en présence d’indices forts pour confirmer le point 2 de la thèse de Toffoli : à chaque équation de la physique semble correspondre un comportement microscopique élémentaire, que l’on modélise ici par un automate cellulaire. Comment trouver les règles de correspondance ? Il n’y a, pour l’instant, aucune méthode systématique. Toffoli donne un indice qui peut servir de guide dans cette recherche :

« Les éléments à rechercher et à garder précieusement, si nous voulons échapper aux pertes que constituent l’uniformisation en gris au niveau macroscopique, sont les symétries et les lois de conservation du niveau microscopique »[46]  [Toffoli94].

Il apparaît ici clairement un parallèle avec le théorème de Noether qui stipule qu’à chaque symétrie microscopique correspond une symétrie macroscopique. Le problème est que ce théorème a été établi pour les milieux continus et n’a à ce jour aucun équivalent dans le domaine discret. Un grand axe de recherche en physique a donc pu émerger de la simple question : comment bâtir un « dictionnaire de correspondances » entre les règles microscopiques et les comportements macroscopiques ?

2. Au cœur de la biologie

Le problème de l’auto-reproduction et le fonctionnement des cellules

Avant de commencer ce nouveau paragraphe, il convient de noter l’existence d’une ambiguïté autour du mot ‘description’. En français, ‘description’ désigne autant le signifiant que le signifié. Ainsi, si l’on dit ‘La description de l’immeuble des Rougon se trouve page 15’, on réfère à la suite de mots qui réalise la description, il s’agit du signifiant. Par contre, si l’on ajoute ‘Cette description est élégante’, on n’entend pas signifier que l’écriture qui est utilisée dans le livre est élégante mais bien que l’auteur utilise un style qui nous plaît. L’anglais utilise ‘blueprint’ pour désigner le support de la description, donc le signifiant, mais ce mot sert aussi pour désigné le signifié. Par exemple, Poundstone écrit: « When it comes to make a new blueprint, the new blueprint is its own blueprint » [Poundstone85, p.188]. Il nous semblerait plus correct de dire “When it comes to make a new blueprint, the new blueprint is its own description”, étant entendu que ‘description’ est utilisé uniquement pour désigner le signifié.

Nous avons vu dans la première partie que le problème central de l’auto-reproduction était d’éviter la régression à l’infini dans la description de soi : la description ne doit pas se décrire elle-même et pourtant l’organisme engendré doit comporter la même description que l’organisme générateur. On ne peut en effet se contenter de donner la description d’une machine auto-reproductrice à un constructeur universel. Le constructeur universel interprétera chaque instruction de la description, construira la machine en question, mais sans reproduire la description qu’il interprète, le résultat est que la machine obtenue a tout pour pouvoir s’auto-reproduire, sauf la description d’elle-même ! La solution de von Neumann fut d’ajouter une unité de supervision qui, elle, était capable de distinguer la phase de construction de la phase de reproduction. Lorsque la phase de construction de la progéniture est terminée, l’unité de supervision ordonne de copier intégralement la description sans chercher à la comprendre. Le prix à payer est que le code de la description est plus long puisqu’il doit également engendrer l’unité de supervision. En revanche, on évite la régression à l’infini puisque la description n’a plus à se décrire elle-même.

Toutes ces considérations peuvent paraître bien théoriques. Puisque nous connaissons effectivement des machines auto-reproductrices qui sont les êtres vivants et leurs cellules, nous sommes en droit de nous demander si de tels mécanismes sont également présents dans la nature. Si les cellules vivantes utilisent d’autres techniques pour s’auto-reproduire, et si ces techniques sont plus simples que celles qu’utilise von Neumann, nous pourrons conclure que la validité de notre modèle se restreint à la logique. Si au contraire, il s’avère que les cellules ont des mécanismes d’auto-reproduction qui sont analogues à ceux imaginés par von Neumann, alors on ne pourra qu’être admiratif devant le fait qu’on puisse découvrir les mécanismes de la vie à partir de raisonnements logiques. L’auto-reproduction décrite par von Neumann et d’Ulam a-t-elle un quelconque rapport avec l’auto-reproduction telle qu’elle se produit dans la nature ?

La réponse à cette question est sans appel. Poundstone écrit ainsi :

« La solution de von Neumann est une belle astuce, mais elle est bien plus que cela. Elle constitue la méthode par laquelle la vie authentique, organique se reproduit. »[47] [Poundstone85, p.189]

Il s’avère qu’il existe ainsi dans les cellules vivantes un équivalent de la description / de l’unité de supervision / du constructeur universel.

Nous allons maintenant étudier les analogies entre le modèle d’auto-reproduction de von Neumann et ce qui se passe réellement dans les cellules vivantes. Nous pouvons noter que toutes les cellules vivantes, quelle que soit l’espèce biologique dont elles sont issues, et quelque soit leur fonction, utilisent le même mode auto-reproduction. L’équivalent de la description est l’ADN : l’ADN contient une description complète de la cellule à l’exception de l’ADN lui-même[48]. Ce qui va jouer le rôle du constructeur universel au sein de la cellule est le ribosome. L’information est transmise aux ribosomes par l’intermédiaire de l’ARN messager. Il se pose néanmoins un problème épistémologique qui concerne la définition de la propriété de constructibilité universelle. Idéalement, le constructeur universel doit être capable de construire tout ce qu’on peut lui décrire. Dans le cas des ribosomes, il s’agit de toute protéine résultant de l’assemblage des vingt acides aminés de base. Ceci veut dire que l’on ne peut synthétiser tout produit imaginable (du plastique), cela va de soi, mais il existe également d’autres organites vitaux qui ne pourront être construits par les ribosomes. C’est le cas de l’hémoglobine, de l’ADN et de l’ARN, qui ne sont pas des protéines. Comment donc décider si un organite possède ou non la propriété de constructibilité universelle ? Poundstone dans [Poundstone85] affirme que le critère le plus important est celui de la participation à l’auto-reproduction non-triviale. Ainsi, si la cellule réussit à s’auto-reproduire, c’est que les ribosomes construisent des enzymes, qui à leur tour vont pouvoir synthétiser les parties indispensables au fonctionnement de la cellule. En particulier, il existe une cellule spéciale, appelée ADN polymérase, qui a la charge de copier l’ADN, sans l’interpréter. Cette enzyme est l’équivalent de l’unité de copie de l’automate auto-reproducteur de von Neumann. Les correspondances entre les processus biologiques et la théorie informatique de von Neumann sont frappantes, d’autant plus qu’au moment des travaux de ce dernier, les mécanismes biologiques n’étaient pas encore connus. Poundstone affirme que la seule différence majeure tient dans l’organisation temporelle des processus : dans le modèle informatique la machine se duplique elle-même (sans sa description) puis s’occupe de copier la description alors que dans le cas de la cellule les deux mécanismes sont simultanés. Les automates cellulaires permettent donc de joindre deux sciences que l’on aurait pensé a priori éloignées : la logique et la biologie. On pourra relativiser en disant qu’on ne fait jamais que continuer dans un grand mouvement que l’on peut faire remonter à Aristote ; pourtant il nous semble clair que l’approche du problème du vivant par le biais de la logique n’a jamais été aussi précise.

Qu’est-ce que la vie ?

Nous pouvons continuer dans cette optique et étudier la question philosophique : « Comment définir la vie ? ». Il est remarquable que les discussions autour de l’élaboration d’une définition précise de la vie restent vives. En effet, il existe toujours des cas qui invalident telle définition où nous obligent à reconnaître qu’elle est partielle. Par exemple, un biologiste sera naturellement amené à définir la vie en fonction décrivant le comportement des molécules carbonées, des acides aminés, des cellules, etc. Il s’agit d’une vision centrée sur ce qu’on connaît de la vie sur terre, mais pourquoi ne pas imaginer que la vie puisse naître sur d’autres supports ? Si à l’opposé on se contente de dire que ce qui caractérise la vie est le processus de reproduction, alors il faut admettre qu’un cristal en croissance est en vie puisque ses formes peuvent aussi se reproduire dans un milieu adéquat. Un autre cas problématique a été inventé par le généticien L. S. Penrose. Dans l’expérience qu’il propose, on dispose de pièces toutes identiques rangées dans une boîte, en long les unes à côté des autres, en alternant leur sens (pièces en position dessus, pièce en position dessous). Si l’on secoue la boîte, les pièces se cognent et il ne se passe rien. Si en revanche, on prend la peine d’accrocher deux pièces consécutives (position dessus et position dessous) et former ainsi un motif, on s’aperçoit que les pièces adjacentes s’accrochent à leur tour et forment le motif initial. L’information se propage de proche en proche et le motif apparaît sur toute la longueur de la boîte[49] [Poundstone85, p.129]. Incontestablement, il y a donc eu auto-reproduction du motif de base. Comment donc distinguer de façon rigoureuse ces cas problématiques des organismes que l’on considère classiquement comme « vivants » ?

Von Neumann a proposé de résoudre le problème en distinguant l’auto-reproduction « triviale » de l’auto-repoduction « non triviale », qui seule est caractéristique de la vie. D’après ses travaux, que nous avons analysés en partie I, on pouvait la définition suivante de la vie :

(1)   Un système vivant contient une description complète de lui-même.

(2)   Il ne contient pas de description de sa propre description. La description sert doublement, soit comme jeu d’instruction, soit comme support pouvant être copié.

(3)   Il existe une partie du système, l’unité de supervision qui s’occupe de la façon d’utiliser la description dans ces deux rôles.

(4)   Une autre partie du système, le constructeur universel, possède la propriété de construire un très grand nombre d’objets à partir des instructions adéquates.

(5)   La reproduction a lieu lorsque l’unité de supervision ordonne au constructeur universel de faire une copie du système qui comporte la description.

Cette définition a l’avantage de ne jamais mentionner la moindre caractéristique physique de l’organisme vivant - elle ne comporte aucune référence au carbone, à l’eau, ni même à la matière - ce qui fait qu’on a pu la qualifier de définition de la vie du point de vue de la théorie de l’information [Poundstone85]. Elle a aussi le mérite d’être claire et de résoudre sans ambiguïté quelques cas problématiques, comme ceux des cristaux ou des motifs de Penrose. Elle stipule aussi clairement qu’un virus n’est pas un organisme vivant puisque ne possédant pas son propre appareil de reproduction. En revanche, on pourra lui reprocher d’éluder de nombreux aspects essentiels du vivant, citons par exemple :

·        leur capacité à résister aux perturbations dues à l’environnement (autopoièse, homéostasie),

·        leur interaction avec l’environnement,

·        leur métabolisme, etc.

D’après Poundstone, l’intérêt philosophique de la construction de von Neumann est d’avoir ôté les derniers doutes quant à la pertinence des théories vitalistes qui, depuis Aristote, soutenaient que la matière vivante contenait une « force vitale », qui lui donnait une particularité que ne possédait pas la matière inerte. Les travaux de von Neumann semblent en effet avoir démontré que la vie pouvait résulter d’une mécanique réglée par les lois de la physique et par elles seules, alors que les mécanismes biochimiques ne commenceront réellement à être élucidés qu’avec la découverte de la structure de l’ADN en 1951. Ces travaux ont aussi mis en évidence l’existence de ce que von Neumann nommait une « barrière de la complexité », qui séparerait les organismes utilisant l’auto-reproduction « non-triviale » des phénomènes qui s’auto-reproduisent, ou s’auto-entretiennent, de façon « triviale ». Ceci infirmerait le point de vue développé par le Comte de Buffon au XVIIIe siècle, et généralement admis par la majorité des savants selon lequel on peut « descendre par degrés insensibles de la créature la plus parfaite jusqu’à la matière la plus informe, de l’animal le mieux organisé jusqu’au minéral le plus brut » [Buffon]. Si la « barrière de complexité » possède une valeur pour caractériser les êtres vivants, une question reste alors posée : Comment la nature a-t-elle procédé pour franchir cette ‘barrière de complexité’ ? Par un procédé graduel ou à l’aide d’un saut qualitatif ? Il nous semble que cette question a très peu été débattue dans les débats qui touchent à l’origine de la vie.

3. La compréhension des phénomènes d’émergence

Réductionnisme et émergence

Les AC fournissent un exemple idéal pour étudier les propriétés d'émergence. Ces propriétés sont généralement illustrées par la formule "le tout est plus que la somme des parties" (1890) que l'on doit au psychologue autrichien Christian von Ehrenfels [Bergandi2000]. On peut dire que l’émergence s’oppose au réductionnisme qui consiste à étudier un problème le décomposant en problèmes plus petits. Cette position épistémologique peut se lire dans les préceptes de Descartes par exemple, dans son Discours de la méthode et on peut dire que tous les scientifiques commencent par décomposer les entités qu’ils manipulent en entités plus petites pour essayer de comprendre les phénomènes qu’ils étudient. Ce qui est moins clair, et ce qui divise les savants, c’est de savoir si cette attitude suffit à résoudre les problèmes scientifiques. On peut résumer le credo réductionniste ‘naïf ‘ comme suit : on ne connaîtra les lois qui règlent les sociétés qu’en étudiant les individus qui la composent, on connaîtra les lois qui règlent les individus qu’en étudiant leur biologie, on ne connaîtra les lois de la biologie que lorsqu’on connaîtra celles de la chimie, etc. Les lois de la chimie elles-mêmes peuvent être déduites des lois de la physique, le stade ultime étant que les lois de la physique peuvent se ramener aux lois de la physique des particules. Même si cette vision des sciences interpelle, le réductionnisme est pourtant le modèle triomphant dans la science moderne. Il est au cœur de nombreux enjeux de société, citons par exemple celui de la psychologie : l’étude du comportement humain doit-elle être confiée aux psychologues qui se passent de connaissances biologiques, aux neurologues, aux spécialistes des sciences cognitives ? Vincent Bauchau, dans un article intitulé « Emergence et réductionnisme : du Jeu de la Vie aux sciences de la vie » écrit ainsi :

« Réductionnisme et émergence sont deux concepts liés l’un à l’autre qui sont soit rejetés parce que triviaux, soit font l’objet de longues discussions philosophiques. Ces deux problèmes ne sont pas seulement débattus par des philosophes, ils constituent aussi matière à controverse au sein des scientifiques (e.g. Weinberg contre Mayr). Comment se fait-il que les scientifiques ne peuvent pas s’accorder sur ces problèmes qui, après tout, sont au centre de leur activité ? » [Bauchau99, p.227].

Ce qui manque probablement pour commencer à créer un consensus, voire une théorie de l’émergence de la complexité, c’est un paradigme établi. Or, les scientifiques qui ont étudié les automates cellulaires s’accordent généralement pour déclarer « qu’ils constituent probablement les meilleurs outils pour étudier l’émergence de la complexité[50] » [Bauchau99]. Dans le cas du Jeu de la Vie, on s’aperçoit par exemple qu’il suffit de laisser tourner une simulation initialisée aléatoirement pour voir apparaître des figures stables. On peut se demander ce qu’il adviendrait pour une simulation qu’on laisserait tourner suffisamment longtemps dans une grille très grande. Verrait-on apparaître des êtres de plus en plus évolués ? Conway n’a pas hésité à répondre par l’affirmative, en ajoutant que des organismes auto-reproducteurs apparaîtraient, évolueraient, écriraient des thèses... Aussi surprenante que soit cette idée, nous devons admettre qu’elle n’est pas plus insensée que de dire que des atomes peuvent se grouper en entités intelligentes.

            Les simulations réalisées à l’aide des automates cellulaires peuvent donc nous montrer des exemples de sélection naturelle. Il existe d’autres classes de modèles où l’on voit opérer la sélection naturelle ; citons par exemple les ‘algorithmes génétiques’. La différence fondamentale est que dans le cas des algorithmes génétiques, on programme le processus de sélection naturelle dans le but de trouver des solutions optimales, alors que dans le cas des automates cellulaires, la sélection naturelle n’est a priori écrite nulle part. Qui prétendrait en effet voir la moindre allusion à des objets ou à des individus dans les règles de Life (cf. I.2) ? Si nous acceptons le fait que les AC soient un modèle du monde physique, nous nous apercevons que la loi de la sélection naturelle existe alors qu’elle n’est écrite nulle part dans les lois de la physique. Nous sommes dans un cas typique d’émergence, dans lequel l’observateur voit apparaître des concepts nouveaux et des lois nouvelles, sans que ces lois ne soient déductibles à partir du niveau inférieur de description.

Le concept de loi

            Néanmoins, on peut légitimement se demander si la sélection naturelle peut acquérir aussi facilement le statut de loi. En parlant de sélection naturelle, les savants écrivent : « Tout se passe comme si la nature choisissait de conserver les individus les plus aptes à survivre » [Heudin, p. 139]. « Le tout se passe comme si »[51] de Kant nous fait retrouver là une grande question philosophique qui est celle de savoir s’il existe une finalité dans la nature. Le débat dépasse de loin le cadre de ce mémoire, et il serait présomptueux d’affirmer que les automates cellulaires permettent de donner une réponse définitive. Néanmoins, ils constituent sans aucun doute un outil formidable pour qui veut fonder sa réflexion sur des expériences concrètes. Le débat de la finalité de la nature passionne encore les scientifiques, les épistémologues ainsi qu’un public initié, comme le témoignage d’un numéro spécial de la revue Sciences et Avenir [Sciences&Avenir2000].

L’approche par AC nous invite aussi à interroger le concept même de loi. L’idée naïve d’une loi est qu’elle est un énoncé universel qui dicte le comportement d’entités. Le Petit Larousse donne, pour le sens qui nous intéresse définit ainsi le concept de loi: « Proposition générale énonçant des rapports nécessaires et constants entre des phénomènes physiques ou entre les constituants d’un ensemble. » ; quant au Petit Robert, il énonce : « III. (1690). Formule générale énonçant une corrélation entre des phénomènes physiques, et vérifiée par l’expérience. IV. Principe essentiel et constant, condition sine qua non [...]». La majorité des épistémologues s’accorde en partie avec ces définitions et signalent que l’universalité n’est pas un critère suffisant pour attester de la validité d’une loi. Hempel donne le contre-exemple suivant : « Tous les corps purs en or massif ont une masse inférieure à 100 00 kg » [Hempel66]. Le concept de loi implique donc l’idée de nécessité, de condition sine qua non. Des épistémologues, tels que van Fraassen ont montré que cette idée de nécessité pouvait conduire à des situations inextricables ; et il va même jusqu’à préconiser l’abandon pur et simple du concept de loi pour celui de symétrie [vanFraassen89]. Ceci s’explique en partie par la constatation suivante : le monde a été créé tel qu’il est et il nous est impossible ni de changer ses conditions initiales ni de changer ses lois (si elles existent). Nous affirmons que le paradigme des AC[52] ouvre des perspectives épistémologiques pour sortir de cette impasse en se plaçant dans contexte pluri-mondain tel que l’a pensé Leibniz[53] : chaque automate cellulaire constituerait un univers à part entière et les lois de la physique ainsi que les conditions initiales de cet univers pourraient être décidées par l’expérimentateur. C’est d’ailleurs ce que font concrètement les chercheurs qui étudient des espaces d’AC (Wolfram, Langton, etc.) : ils décident des règles de l’automate cellulaire et initialisent le monde avec une configuration de leur choix[54]. Dans ce contexte, des résultats surprenants sont obtenus : la sélection naturelle n’est même plus une loi fondamentale puisqu’il existe des mondes[55] dans lesquels cette « loi » n’est pas valide. L’emploi du paradigme des AC nous conduit donc à nous interroger sur l’émergence de la complexité dans notre univers en repartant des bases même de la physique, de l’épistémologie et de la logique.

La genèse des formes

Dans les chapitres qui précèdent, une question omniprésente, bien que sous-jacente, a été celle de l’origine des formes. Nous l’avons rencontrée lors des discussions autour des formes auto-reproductives, des formes stables, des formes qui rappellent des phénomènes connus comme les domaines magnétiques ou les feux de forêt. Cette question se retrouve lorsqu’on cherche à comprendre les mécanismes de différentiations cellulaires : Comment en partant d’une situation constituée d’une unique cellule est-il possible de construire un individu dont les cellules sont différenciées [Turing52]?

Outre les systèmes biologiques, de nombreux systèmes physiques possèdent cette capacité de genèse des formes. L’inconvénient dans une étude physique est qu’on ne maîtrise pas toutes les données en jeu et que l’on doit sélectionner certains paramètres qu’on pense être pertinents. En cristallographie par exemple, si l’on observe que des atomes s’organisent en un réseau cristallin, on explique ce phénomène en termes de nuages électroniques et d’énergie du système. Les atomes sont considérés comme des sphères isotropes et on ne fait jamais appel à une quelconque forme des atomes pour expliquer la forme du réseau. Pourtant, le doute est permis : et si les atomes avaient réellement une forme et si c’était leur forme qui expliquait celle du réseau ? Cette hypothèse est bien entendu fantaisiste mais elle a le mérite de montrer que dans toute expérience faisant intervenir des entités physiques, l’explication de l’émergence d’une forme peut donner lieu à controverse. Citons par exemple les travaux de Turing relatifs à la morphogenèse [Turing52] : les substances morphogénétiques introduites étaient une pure spéculation, un moyen mathématique pour expliquer la différenciation cellulaire. Très longtemps, le doute a plané sur la réalité de ces substances et ce n’est qu’à l’aide de travaux récents que l’on a réussi à montrer l’existence de mécanismes analogues à ceux décrits par Turing.

L’utilisation des AC permet d’éviter qu’il y ait le moindre doute quant à l’origine des formes : avec les AC le concepteur de l’automate a toutes les données en main. Il ne peut donc pas justifier son ignorance sur l’origine des formes qu’il observe en prétendant qu’il ne possède qu’une connaissance imparfaite de son système : chaque donnée peut être connue de lui. La question de l’origine des formes et de l’évaluation de leur complexité est très vaste, elle peut être traitée sous de nombreux angles. Un paramètre qui nous semble important à étudier dans la théorie des AC est la capacité d’un automate à faire apparaître des formes En se fondant sur les travaux précédemment examinés, notamment [Toffoli94] et [Bauchau99], nous pensons que l’utilisation des AC pourra apporter de nombreux éclaircissements à cette question, notamment à l’aide de l’étude des variations de l’entropie des systèmes avec le temps. Nous clorons donc ce chapitre proposons une classification des automates cellulaires basée sur la notion d’entropie :

Cette classification fait ressortir le fait que la propriété de calculabilité universelle ne peut plus être cantonnée aux domaines de la logique et de l’informatique fondamentale. Vue sous l’angle de la classification proposée, cette propriété devient une caractéristique (la plus haute) d’un système physique et apparaît comme une propriété à rechercher en partant de l’étude microscopique des phénomènes. Aussi, nous adhérons au point de vue exprimé par Bauchau :

« Appliquer des règles simples pour créer une dynamique complexe est possible, comme le montrent, par exemple, les systèmes chaotiques. D’autres systèmes où la complexité émerge à partir des règles simples sont ceux, tel le Jeu de la Vie, qui sont capables de computation universelle. Cette classe de systèmes est connue depuis longtemps mais a reçu moins de publicité. Dans ces systèmes, bien que les règles et les états initiaux soient parfaitement connus, l’existence de caractéristiques imprévisibles et irréductibles peut être prouvée formellement. L’importance de propriétés ‘fortes’ dans les systèmes vivants est sans doute matière à spéculation, mais il s’agit au moins d’une possibilité logique qui, je crois mériterait plus d’attention. » [Bauchau99, p.242]

Dans cette optique, il devient pertinent de poser des questions telles que : « Le système de genèse de formes vivantes par différentiation des cellules est-il doué de la propriété de calculabilité universelle ? ». Si oui, une conséquence pratique, et de taille, est qu’un tel système sera ‘fortement’ imprévisible et qu’il ne pourra être caractérisé qu’à l’aide de simulations gigantesques. Nous voyons là en apparaître en filigrane un changement épistémologique de taille : des questions qui étaient autrefois réservées aux systèmes logiques et informatiques sont posées au sujet de systèmes physiques et biologiques.

CONCLUSION

Ce mémoire nous a permis de retracer l’histoire des automates cellulaires, depuis leur invention dans les années 50 jusqu’aux recherches plus récentes. Tout d’abord conçus pour répondre à un problème bien spécifique, celui de la construction d’un automate auto-reproducteur, les AC ont été un prétexte à un grand mouvement de recherche initié avec le Jeu de la Vie. Ils se sont ensuite en quelque sorte « émancipés » et leur intérêt comme classe de modèles s’est fait ressentir dans un grand nombre de domaines scientifiques allant de la physique aux sciences humaines, gagnant par-là le statut de paradigme scientifique. L’histoire des automates cellulaires part donc de l’étude d’un AC particulier dédié à un but articulier (von Neumann, Codd), se développe lors de l’étude d’un AC conçu comme un jeu (Conway), puis se généralise comme classe de modèles (Wolfram, Langton, etc.). L’histoire des AC suit donc un mouvement de généralisation croissante jusqu’à la constitution d’un paradigme. Néanmoins, les utilisateurs des automates cellulaires restent des précurseurs et force est de reconnaître que leur usage ne s’est pas encore répandu dans les milieux scientifiques et industriels. Faire appel à un automate cellulaire pour résoudre un problème scientifique ne va pas de soi.

La raison probable de cet engouement relativement faible des chercheurs pour leur utilisation est la difficulté que nous avons dans la compréhension des phénomènes impliquant le parallélisme. Nous sommes généralement désarmés lorsque nous devons construire un modèle qui prédit l’évolution de nombreux paramètres dans l’espace et le temps. Comme le signale un chercheur qui utilise les automates cellulaires dans la modélisation de la dynamique urbaine, les premiers modèles de peuplement en géographie se concentraient sur des données telles que la population, la densité et, comble du paradoxe, oubliaient la répartition dans l’espace proprement dite [Langlois97]. L’élaboration d’une théorie des automates cellulaires est donc un enjeu scientifique majeur pour la compréhension de tous les phénomènes dans lesquels le parallélisme est une caractéristique fondamentale ; et à bien y regarder, on s’aperçoit qu’il s’agit de la majorité des phénomènes.

L’enjeu n’est d’ailleurs pas seulement scientifique mais aussi technique : au XXIe siècle l’environnement semble se modeler à l’image des réseaux et il est probable que les résultats théoriques obtenus avec les AC pourront influencer considérablement l’état des techniques. Une condition nécessaire à l’explosion des AC est la maîtrise des architectures d’ordinateurs parallèles : à quoi bon en effet simuler le fonctionnement d’une machine parallèle sur une machine séquentielle ?

Un autre trait remarquable de cet outil est que malgré son aspect fondamentalement mécanique (c’est l’aspect automate), les chercheurs qui étudient les univers cellulaires ont une attitude de naturalistes : la recherche de régularités se fait essentiellement à l’aide de l’observation (c’est l’aspect cellulaire). Pourtant, dans une construction qui est faite avec un automate cellulaire, tout est maîtrisé, du moins dans la situation initiale. On pourrait donc penser que la maîtrise du déroulement d’un AC conduit à faire des expériences ennuyeuses où tout ou presque peut être prévu d’avance. En vérité on s’aperçoit que c’est tout le contraire. Nous avons vu que des règles aussi simples que celles de Life peuvent conduire à des comportements imprévisibles et inattendus. Aussi, l’étonnement surgit pour toute personne qui regarde évoluer un automate cellulaire non trivial. Pour celui qui programme Life, le modèle d’Ising ou celui des feux de forêt, la question : «  Comment est-ce possible de capter un comportement aussi riche en utilisant si peu de lignes de programmation ? » surgira immanquablement. Qu’il s’agisse de définir ce qu’est la vie, de comprendre l’origine de la complexité de l’univers ou de mieux cerner la notion de loi de la nature, nous avons vu que les AC par leur aspect minimaliste nous obligent à aller au fond des problèmes : leur utilisation invite au questionnement philosophique. Il nous semble donc probable que les automates cellulaires retiendront une part grandissante de l’intérêt des philosophes des sciences. Nous pensons que les automates cellulaires sont un domaine de recherche d’avenir, qui n’a encore livré que quelques secrets. Idéalement, l’étude des automates cellulaires conduira autant à mieux comprendre les phénomènes qu’à s’interroger sur la façon dont nous comprenons ces phénomènes ; il est donc probable que cette classe de modèles abstraits serve de lien entre scientifiques et épistémologues. L’étude des automates cellulaires peut être ramenée dans un cadre plus vaste, celui des sciences dites de « la complexité », qui incluent l’étude des systèmes dynamiques chaotiques, la théorie de la morphogenèse, la vie artificielle, etc. Chacun de ces domaines possède ses propres paradigmes et les connexions entre eux restent très faibles. Nous pouvons dire que le seul lien fondamental entre les disciplines des sciences de la complexité est d’utiliser l’ordinateur comme outil fondamental Il n’y là apparemment rien d’extraordinaire mais nous pouvons sentir un changement radical dans la vision de la science : alors que les savants s’interrogent depuis l’antiquité si le monde est écrit en langage mathématique, un nouvel enjeu philosophique tend à émerger : celui de savoir si le monde est écrit en langage algorithmique. A Leibniz, qui en marge d’un dialogue écrit en 1677  : Cum Deus calculat et cogitationem exercet, fit mundus : « Tandis que Dieu calcule et exerce sa cogitation, le monde se fait. » ; nous sommes désormais tentés de dire : « Tandis que Dieu calcule (effectue) des algorithmes et exerce sa cogitation, le monde se fait »[56].

REFERENCES BIBLIOGRAPHIQUES

[Ball98] P. Ball, The Self-Made Tapestry, Oxford University Press, 1998.

[Bauchau99] V. Bauchau, « Emergence et réductionnisme : du Jeu de la Vie aux sciences de la vie » in Auto-Organisation et émergence dans les sciences de la vie, sous la dir. de B. Feltz et al., Editions OUSIA, distribution à Paris : Vrin, 1999.

[Bergandi2000] D. Bergandi, « L’idée d’émergence », in Sciences et Avenir Hors-Série Les grandes idées du siècle, Janvier 2000.

[Buffon] Comte de Buffon, De la manière d’étudier et de traiter l’histoire naturelle - Oeuvres Complètes, 1774-1779.

[Codd68] E. F. Codd, Cellular Automata, New York Academic Press, 1968.

[Culik88] K. Culik, S. Yu, “Undecidability of CA classification schemes”, Complex Systems, 2, p.177, 1988.

[Berlekamp&Al.82] E. Berlekamp, J. Conway, G. Richard, Winning ways, vol. 2 , New York : Academic Press, chap. 25, 1982.

[Galam98] S. Galam, « Sous les chemises... La symétrie » in Dossier Pour la Science - Les symétries de la nature, Juillet 1998.

[Gandy78] R. Gandy, “Church's thesis and principles for mechanisms” (1978), The Kleene Symposium, Edité par J. Barwise& al,. North-Holland Publishing Co., Amsterdam-New York, 1980.

[Gardner70] M. Gardner, "Mathematical Games: The fantastic combinations of John Conway's new solitaire game ‘life’", Scientific American, pp. 120-123, Octobre1970.

[Goujon99] Ph. Goujon,“De la logique à l’auto-organisation”, » in Auto-Organisation et émergence dans les sciences de la vie, sous la dir. de B. Feltz et al., Editions OUSIA, distribution à Paris : Vrin, 1999.

[Hempel66] C. Hempel, Eléments d’épistémologie (1966), Paris: Armand Colin / Masson, 1996.

[Heudin97] J-C. Heudin, M. Magnier, C. Lattaud, « Complexity classes in the Two-dimensional Life Cellular Automata Subspace », Complex Systems, N° 11, pp.419-436, 1997.

[Heudin98] J-C. Heudin, L’évolution au bord du chaos, Paris : Hermès, 1998.

[Kant] E. Kant, Critique de la Raison Pure (1781), Paris : PUF/Quadrige, 1997.

[Kuhn70] T. Kuhn, La structure des révolutions scientifiques (1970), Flammarion, 1983.

[Langton84] C. G. Langton, “Self-Reproduction in Cellular Automata”, Physica D, n°10, pp. 135-144, 1984.

[Langlois97] A. Langlois, M. Phipps, Automates Cellulaires - Application à la simulation urbaine, Paris : Hermès, 1997.

[Langton90] C.G. Langton, “Computation at the edge of chaos : phase transition and emergent computation”, Physica D 42, pp. 12-37, 1990.

[Leibniz] G.W. Leibniz, Oeuvres, édition Gerhardt, Berlin 1875-1890, tome VII, p.191 cité in Gérard Chazal, Formes, Figures, Réalités, Champ Vallon, 1997.

[Moore62] E. Moore, “Machine models of self-reproduction.” in Proc. Symposia Applied Mathematics, Vol. XIV, Amer. Math. Soc. , pp.17-34, 1962.

[Moore64] E. Moore, Sequential Machines, Selected Papers, Addison Wesley, 1964.

[Odifreddi89] P. Odifreddi, Classical Recursion Theory, North-Holland, 1989.

[Poundstone85] W. Poundstone, The Recursive Universe, Oxford University Press, 1985.

[Sciences&Avenir2000] Sciences et Avenir, Hors-Série : « La finalité dans les sciences, Le sens de la vie », Octobre-Novembre 2000.

[Time74] “The Game of Life”, Time, 21 Janvier 1974.

[Toffoli94] T. Toffoli, “Occam, Turing, von Neumann, Jaynes: How much you can get for how little ? ( A conceptual introduction to cellular automata )”, InterJournal, Décembre 1994.

[Turing36] A.M Turing, “On Computable Numbers, with an application to the Entscheidungsproblem”, Proceedings of the Mathematical Society, Série 2, Vol. 42 (1936-1937), p.230-265.

[Turing52] A.M Turing, “The chemical basis of morphogenesis”, Philosophical Transactions of the Royal Society, N° 237, 1952.

 [Turing54] A.M Turing, “Solvable and unsolvable problems”, Science news 31, 1954.

réimp. in Collected works, Pure mathematics, pp. 99-115, 261-263.

[Ulam50] S. Ulam, "Random Processes and Transformations", in: S. Ulam, Sets, Numbers and Universes, Cambridge : MIT Press , pp. 326-337, 1974.

[vanFraassen89] Bas C. Van Fraassen, Lois et Symétries (1989), Paris : Vrin, 1994.

[vonNeumann66] John von Neumann, Theory of Self-Reproducing Automata, Urbana : University of Illinois Press, 1966.

[Wolfram83] S. Wolfram, « Statistical Mechanics of Cellular Automata » in Review of Modern Physics 55, pp.601-644, 1983.

[Yunes93] J.B. Yunès, Synchronisation et automates cellulaires : la ligne de fusilliers, Thèse présentée à l’université Paris 7, 17 février 1993.

ANNEXES