Automates cellulaires : dynamiques, simulations, traces

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é23 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 dont la maison m’a permis des pauses agréables, ainsi qu’à ma famille élargie, pour sa présence à Paris.4Table 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6 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 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Introduction 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ées quarante [1]. Intéressé par l’idée de l’autoréplication des robots, il adapte l’univers discret dans lequel son collègue Stanisław Ulam modélise la croissance des cristaux. Il en résulte une grille bidimen- sionnelle dont chaque cellule peut prendre un état parmi vingt-neuf possibles, état qui va évoluer à chaque instant en fonction de l’état de ses plus proches voisines. Cette définition est donc très simple, et le sera encore plus avec les variantes de Codd [2] ou Langton [3]. Elle laisse cependant déjà apparaître des comportements étranges, tel que des motifs particuliers qui sont capables de se reproduire eux-mêmes indéfiniment. Cette idée d’univers discret conduisit Konrad Zuse à penser en 1967 que les lois de la physique sont régies par un gigantesque automate cellulaire, créant ainsi la physique digitale [4]. Mais c’est surtout dans les années soixante-dix que les automates cellulaires seront popularisés, par le «jeu de la vie» de John Conway [5]. Il consiste en des cellules qui naissent, survivent ou meurent en fonction du nombre de leurs voisines. Avec une règle là encore très simple, on parvient à des structures pouvant avoir une évolution étrange; ce phénomène sautera rapidement aux yeux de la communauté informatique naissante, sa simplicité en faisant un exercice classique de programmation. Il sera form