Automates cellulaires : dynamiques, simulations, traces, Cellular automata : dynamics, simulations, traces

Pierre Guillon

Description

Sous la direction de Enrico Formenti, Julien Cervelle
Thèse soutenue le 24 novembre 2008: Paris Est
Un automate cellulaire est un système dynamique discret qui modélise des objets ayant une évolution parallèle synchrone: l'espace est divisé en cellules ayant chacune un état et qui évoluent toutes selon une même règle locale, qui ne dépend que d'un nombre fini de cellules voisines. Malgré la simplicité de la formalisation de ce système, des comportements très complexes peuvent apparaître, qui en font notamment un modèle de calcul. Cette complexité a été rattachée à diverses théories: topologie, mesure, décidabilité, information...Nous adoptons ici une approche basée sur la dynamique symbolique, c'est à dire l'étude des mots infinis sur un alphabet donné auxquels on applique un décalage, suppression de la première lettre. À chaque automate cellulaire peut en effet être associé son tracé, l'ensemble des mots infinis représentant la séquence des états successifs pris par la cellule centrale de l'espace - ou un groupe de cellules centrales. On a alors une factorisation topologique: la lecture d'une lettre dans un de ces mots correspond exactement à une étape de l'évolution de l'automate. De nombreuses propriétés topologiques sont alors transmises par cette factorisation. Inversement, le fait que les cellules évoluent toutes de la même manière permet de déduire certaines propriétés de l'automate à partir de celles de son tracé. La première partie de la thèse est consacrée à ces nombreux liens. Une deuxième partie présente des conditions suffisantes pour qu'un ensemble de mots infinis soit le tracé d'un automate cellulaire. Enfin, une troisième partie donne un point de vue plus informatique, en récapitulant les principaux résultats d'indécidabilité sur le sujet et en prouvant que toutes les propriétés du tracé qui peuvent se voir infiniment tard sont indécidables
-Sous-shift
-Simulation
A cellular automaton is a discrete dynamical system which can model objects that evolve parallelly and asynchronously : the space is divided into cells, each of which has a state evolving according to some single local rule and a finite number of neighboring cells. Though this system can easily be formalized, very complex behaviors can appear ; it turns out to be a powerful computational model. That complexity can be studied with respect to various theories : topology, measure, decidability, information...We adopt here an approach bases on symbolic dynamics, linked to the topology and to the study of shifts of infinite words (suppression of their first letter). To each cellular automaton can be associated its trace subshift, the set of infinite words that represent the sequence of successive states taken by the central cell or some group of central cells. We then have a topological factorisation : reading a letter in one of these words correspond to applying a step of evolution of the automaton
Source: http://www.theses.fr/2008PEST0215/document

Informations

• Publié par: Thesee
• Nombre de lectures: 60
• Langue: Français
• Poids de l'ouvrage: 1 Mo

Extrait

THÈSE
pour obtenir le grade de
DOCTEUR DE L’UNIVERSITÉ PARIS-EST
Automates cellulaires: dynamiques, simulations, traces
Spécialité informatique
École doctorale ICMS
Soutenue publiquement par Pierre Guillon
le 24 novembre 2008
JURY :
Madame Marie-Pierre BÉAL Université Paris-Est examinatrice Valérie BERTHÉ Université de Montpelliere
Monsieur Julien CERVELLE Université Paris-Est directeur de thèse Enrico FORMENTI Université de Nice-Sophia-Antipolis directeur de thèse
Madame Nataša JONOSKA University of South Florida (États-Unis) rapporteuse
Monsieur Luciano MARGARA Università di Bologna (Italie) rapporteur Jacques MAZOYER invité
tel-00432058, version 1 - 13 Nov 20092
tel-00432058, version 1 - 13 Nov 20093
Je remercie tous ceux qui ont permis cette thèse. Merci à mes encadrants, à mes rapporteurs, aux
membres de mon jury. Merci aux professeurs et directeurs de stage qui ont pu m’aiguiller vers ce domaine
passionant.
Je remercie également tous ceux qui ont influencé, plus ou moins consciemment, mon travail. Merci
à tous les participants aux rencontres FRAC, à tous les chercheurs français et étrangers avec qui j’ai pu
discuter. Merci à tous les membres, de domaines variés, du laboratoire d’informatique Gaspard-Monge,
qu’ils m’aient fait part de leurs thématiques, m’aient initié aux sports de roulettes ou m’aient aidé sur
des points techniques ou administratifs précis.
Je remercie enfin tous ceux que j’ai pu cotoyer pendant ces trois années et demie. Merci à mes amis
de Paris ou d’ailleurs, à ma fanfare, à mes colocataires de trois ans ou d’une semaine. Merci à ma petite
famille et à ma famille élargie.
tel-00432058, version 1 - 13 Nov 20094
tel-00432058, version 1 - 13 Nov 2009Table des matières
Table des matières 5
Introduction 7
Notations 13
1 Systèmes dynamiques 17
1.1 Systèmes discrets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.2 Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.3 Opérations sur les systèmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.4 Propriétés immédiates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.5 Dynamiques simples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.6 Transitivité, récurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.7 Chaînes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
1.8 Équicontinuité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.9 Expansivités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.10 Ensembles limites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.11 Entropie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
1.12 Systèmes symboliques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2 Décalages 39
2.1 Sous-décalages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.2 Morphismes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.3 Opérations sur les sous-décalages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.4 Soficité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
2.5 Type fini . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.6 Propriété des sous-décalages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3 Systèmes symboliques et trace 61
3.1 Automates cellulaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.2 Simulation cellulaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.3 Opérations sur les systèmes symboliques . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.4 Tracés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.5 Tracés d’automates cellulaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.6 Classification symbolique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
3.7 D’autres systèmes symboliques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5
tel-00432058, version 1 - 13 Nov 20096 TABLE DES MATIÈRES
4 Dynamique des systèmes symboliques 79
4.1 Propriétés immédiates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.2 Dynamiques simples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
4.3 Transitivité, récurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
4.4 Chaînes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
4.5 Équicontinuité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
4.6 Expansivités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
4.7 Ensembles limites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
4.8 Entropie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
5 Traçabilité 103
5.1 Polytracés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
5.2 Tracés partiels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
5.3 Tracés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
5.4 Bitracés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
5.5 Autres sous-décalages remarquables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
6 Décidabilité 123
6.1 Nilpotence et premières conséquences. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
6.2 Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
6.3 Tracés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
6.4 Décidabilité des systèmes sofiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
Conclusion 137
Index 138
Bibliographie 145
A Caractérisations dynamiques 153
A.1 Propriétés symboliques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
A.2 immédiates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
A.3 Dynamiques stables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
A.4 chaotiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
B Implications entre notions dynamiques 157
C Simulations, traces & dynamiques 161
D English summary 163
D.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
D.2 Dynamical systems and cellular automata . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
D.3 Traces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
D.4 Topological dynamics and traces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
D.5 Traceable subshifts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
D.6 Decidability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
D.7 Generalizations... and restrictions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
tel-00432058, version 1 - 13 Nov 2009Introduction
es fourmis construisant une fourmilière, les neurones qui se transmettent l’influx nerveux dans le cer-
L veau,lesmachinesconnectéesparunréseau,lesautomobilistessetamponnantdansunembouteillage,
sont autant d’éléments petits et stupides qui, malgré la faible portée de leurs interactions, parviennent
à former des systèmes très complexes. Comment une telle complexité peut-elle naître d’objets aussi ba-
siques? Cette question est le point commun entre de nombreux domaines scientifiques : mécanique des
fluides, chimie des turbulences, cristallographie, biologie cellulaire, sciences cognitives, dynamique des
sociétés, réseaux informatiques. En découlent de nombreux problèmes de modélisation, mais surtout,
au-delà, un objet d’étude plus général : la théorie de systèmes complexes.
Automates cellulaires. John von Neumann, tentant de comprendre ces règles primitives qui per-
mettent l’organisation de formes complexes, fut le premier a définir un automate cellulaire à la fin des
anné