Décidabilité

Par exemple, dès la dimension 2, même les propriétés immédiates d’injectivité et de surjectivité sont imprévisibles à partir de la règle locale [13]. Cela vient surtout de l’indécidabilité du problème de lavabilité prouvée par Berger : à partir de la connaissance de contraintes, même très locales, d’agencement d’objets, on ne sait pas décider si l’on va pouvoir recouvrir le plan ; c’est par exemple le cas pour les cellules obtenues par application de l’automate cellulaire. On se restreindra ici toujours aux AC de dimension 1. Dans ce cas, l’injectivité et la surjectivité sont décidables [102, 103] – on peut voir par exemple la surjectivité sur le graphe de Bruijn du fait 2.2.6. En revanche, toutes les propriétés de dynamique à long terme, même les plus simples, sont indécidables. Intuitivement, l’évolution de l’automate cellulaire introduit dans le temps une seconde dimension et la propriété correspond donc à un problème de pavage du plan. Il va de soit que, pour un autre monoïde dans lequel ❩ pourrait être plongé, les problèmes sont au moins aussi compliqués ; les résultats d’indécidabilité sont donc toujours vrais en particulier pour les AC sur des espaces Ason diamètre et sa table de transition qui associe à chaque voisinage un état par la règle locale. Lorsque l’on considérera des algorithmes sur les sous-décalages, on sera bien obligés de se restreindre à des classes représentables : les STF seront représentés par leur liste de mots interdits minimaux, les sous-décalages sofiques par une matrice représentant leur graphe.

Les problèmes indécidables sur les automates cellulaires se ramènent souvent à la nilpotence, prouvée indécidable par Kari dans [12], en y réduisant une version du problème de la pavabilité renforcée en se restreignant aux jeux de tuiles déterministes. Ces derniers correspondent en quelque sorte aux dia- grammes espace-temps d’AC 0-envahissants dans lesquels l’état 0 n’apparaît pas ; celui-ci représente alors l’impossibilité de prolonger le pavage.Indécidabilité à alphabet fixé. L’indécidabilité des propriétés vient de l’infinité des AC en faisant varier deux paramètres : le diamètre et l’alphabet. Lorsque ce n’est pas précisé, on considère donc que nos algorithmes prennent en entrée des AC de diamètre et d’alphabet quelconques ; de manière équivalente, par la simulation de la remarque 3.3.2, on peut fixer un rayon égal à 1 sans que cela n’altère l’indécidabilité d’un problème. En revanche, les résultats d’indécidabilité à alphabet fixé sont plus forts. Nous allons montrer quelques résultats de ce type, en faisant varier le diamètre et en fixant l’alphabet à  – qui peut être plongé dans n’importe quel autre alphabet non trivial.Nous avons déjà remarqué que la nilpotence n’était pas altérée par décalage.

En revanche, la sensibilité l’est au point que tout AC non nilpotent devient sensible quand il est suffisamment décalé (cf proposition 4.5.8). Si l’on disposait d’une procédure de décision pour la sensibilité, on pourrait l’appliquer à tous les automates cellulaires, après les avoir décalé de la valeur de leur rayon, pour savoir s’ils sont nilpotents. L’application de l’AC simule alors F et N indépendamment (première partie de la règle) jusqu’à ce qu’un 0 apparaisse et qu’ils changent tous deux de règle (deuxième partie de la règle) ; ce bouleversement ne peut se produire pour chaque cellule qu’une seule fois, puisque par la suite les lettres de l’alphabet de la composante de gauche restent dans Asimulation cellulaire. Même si l’on a utilisé dans la construction précédente une sous-factorisation cellulaire, il s’avère que N peut être un sous-décalage quelconque, ce qui ne rend pas l’idée d’une simulation effective, i.e. qui impliquerait une restriction plus visuelle. Remplacer la nilpotence par la nilpotence sur les périodiques, comme dans.., va nous permettre d’avoir des configurations non immortelles assez régulières (simulation par blocs).

Par rapport à la proposition 6.2.4, on a donc pu ajouter la condition par blocs, qui est très importante dans l’idée de pouvoir se représenter la simulation intuitivement. Nous avons également vu que l’on pouvait ajouter une condition d’exactitude, mais au prix d’un groupage vertical. Un filtre principal pour une relation de simulation est une classe d’AC qui est stable par la relation «être simulé par» et qui possède un élément, dit minimal, que tous les éléments de la classe simulent. Si on considère une telle classe ne contenant pas d’AC nilpotent sur les périodiques, alors toute procédure de décision représenterait une séparation récursive entre la classe des AC nilpotents sur les périodiques et ceux qui simulent un de ses éléments minimaux.