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).
Von Neumann est indiscutablement un grand génie du XXe 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].
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 tn induit l’état du point au temps tn+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. »