Complexité structurelle et algorithmique des pavages et des automates cellulaires

Jury: Alain Colmerauer, Marianne Delorme, Bruno Durand2, Enrico Formenti, Jean-yves Marion et Michel MorvanThis thesis examines the complexity of tilings and cellular automata. The analysis begins by structural considerations: quasiperiodic tilings. To any set of tiles that tiles the plane, we associate a quasiperiodicity function that quantifies complexity. Firstly, it is shown that any "reasonable" function may be captured by a set of tiles and that there are tilings whose quasiperiodicity function grows faster than any computable function. Then we prove a Rice theorem for tilings: the set of all tile sets that recognize the same tilings as another tile set is recursively enumerable and undecidable. Finally, we transpose our results in the context of cellular automata. The second part of our work concerns the study of cellular automata in terms of dynamical systems, particularly chaotic controllers. The usual definitions classifying chaotic controllers are not satisfactory. To overcome this problem, we use two new topologies. The first is called Besicovitch and removes the dominance of the central pattern in the study of the evolution of the automaton. It brings several results, the first indicating that our new workspace is acceptable to the study of cellular automata as dynamical systems; the latter shows that the notion of chaos remains, through the definition of sensitivity to initial conditions, but the most chaotic classes are empty. The second topology employed is defined using algorithmic complexity. The purpose of this approach is to have a distance that reflects the ease calculating a member from the other. Our results complement the earlier results. They attest formally that cellular automata can not continuously change the information in a configuration, and especially that they are incapable to create information.Ce travail de thèse étudie la complexité des pavages et des automates cellulaires. L'analyse débute par des considérations structurelles : la quasipériodicité des pavages. À tout ensemble de tuiles qui pave le plan, on associe une fonction de quasipériodicité qui quantifie sa complexité. Tout d'abord, on montre que toute fonction ``raisonnable'' peut être capturée par un ensemble de tuiles et qu'il existe des pavages dont la fonction de quasipériodicité croît plus rapidement que n'importe quelle fonction récursive. Ensuite, on démontre un théorème de Rice pour les pavages : l'ensemble des ensembles de tuiles qui admettent les même pavages qu'un autre fixé est indécidable et récursivement énumérable. Enfin, on transpose notre résultat dans le contexte des automates cellulaires. La seconde partie de notre travail concerne l'étude des automates cellulaires sous l'angle des systèmes dynamiques, et plus particulièrement des automates chaotiques. Les définitions usuelles classifiant les automates chaotiques ne sont pas satisfaisantes. Pour palier ce problème, on utilise deux nouvelles topologies. La première est dite de Besicovitch, et permet de supprimer la prédominance du motif central lors de l'étude de l'évolution de l'automate. On apporte plusieurs résultats, les premiers indiquant que notre nouvel espace de travail est acceptable à l'étude des automates cellulaires, en tant que systèmes dynamiques ; les seconds montrent que la notion de chaos subsiste, grâce à la définition de sensibilité aux conditions initiales, mais que les classes plus chaotiques sont vides. La seconde topologie employée est définie à l'aide de la complexité algorithmique. Le but de cette approche est d'avoir une distance qui traduit la facilité à calculer un élément à l'aide de l'autre. Nos résultats complètent les précédents. Ils attestent de manière formelle que les automates cellulaires ne peuvent pas modifier continûment l'information contenue dans une configuration, et surtout qu'ils sont incapables d'en créer