Complexité structurelle et algorithmique des pavages et des automates cellulaires / par Julien Cervelle ; sous la direction de Bruno Durand

Bibliogr. p. 91-93. Index

Thèse de doctorat informatique et mathématiques 2002 Aix-Marseille 1

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. A 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êmes 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