i. une breve histoire des automates cellulaires

Nazim FATÈS
18, rue Solferino
92 170 VANVES
n_fates@scientist.com
DEA Histoire et Philosophie des Sciences
UFR 10 - Paris I Sorbonne
LES AUTOMATES CELLULAIRES : VERS UNE NOUVELLE EPISTEMOLOGIE ?
[pic]
Mémoire de D.E.A - Sous la direction de M. Jean Mosconi
Septembre 2001
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 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 s