Hiérarchies algébriques de classes d'automates cellulaires
Résumé
Cellular automata are a formal model of locally interacting systems which is very simple but suitable to study complex systems in general. Many classifications have been proposed in the literature, often relying on the observation of dynamics. In a first part, we present more recent approaches of algebraic nature based on notions of sub-systems or embeddings. A second part, which is more technical, is dedicated to new results concerning these algebraic tools. This framework allows us to give formal definitions to several intuitive global notions (e.g., universality, particles) and to derive formal proofs of positive results and, more interestingly, of negative results. More precisely, we show that modifying local rules may be more powerful in some sense than increasing the number of states ; then, we illustrate by the construction of an infinite lattice that dynamical universality is incredibly more powerful than usual computation universality.
Les automates cellulaires sont un modèle formel de systèmes définis par interactions locales qui est à la fois très simple et bien adapté à l’étude des systèmes complexes en général. Plusieurs classifications ont été proposées dans la littérature s’appuyant le plus souvent sur l’observation de leur dynamique.Dans une première partie, on présente les approches récentes de nature algébrique fondées sur les notions de sous-systèmes et d’injection. Une seconde partie, plus technique, est dédiée à de nouveaux résultats concernant ces outils algébriques. Ce cadre nous permet de donner des définitions formelles à plusieurs notions intuitives (en particulier, universalité et particules) et d’en déduire des preuves de résultats positifs ainsi, que ce qui est ici plus intéressant, des résultats négatifs. Plus précisément, on montre qu’en un certain sens modifier les règles locales est plus puissant qu’augmenter le nombre d’états ; puis, nous illustrons par la construction d’un treillis infini que l’universalité pour la dynamique est plus puissante que la notion usuelle d’universalité pour le calcul.
| Origine | Fichiers produits par l'(les) auteur(s) |
|---|
Loading...