Les automates cellulaires: vers une nouvelle epistémologie ?

Extraits du mémoire

[...] 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. [...]

[...] 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. [...]

[...] 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. [...]

[...] 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 ? [...]

[...] 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. [...]

[...] 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. [...]

[...] 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 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. [...]

[...] 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. [...]

[...] 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 : 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. La phase é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]. [...]

[...] 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]. [...]