Décidabilité des comportements globaux d’automates cellulaires et d’automates de sables

Les automates cellulaires sont des systèmes dynamiques massivement parallèles régis par une règle locale simple qui peut engendrer un comportement global complexe. Dans cet exposé, nous nous intéresserons à la décidabilité de l’injectivité et de la surjectivité du comportement global à partir de la règle locale. Dans un premier temps, nous présenterons les résultats connus sur les automates cellulaires de dimension 1 et plus ; puis nous nous intéresserons au modèle intermédiaire que sont les automates de sables.