Undecidability of the global fixed point attractor problem on circular cellular automata.
Résumé
A great amount of work has been devoted to the understanding of the long-time behavior of cellular automata (CA). As for any other kind of dynamical system, the long-time behavior of a CA is described by its attractors. In this context, it has been proved that it is undecidable to know whether every circular configuration of a given CA evolves to some fixed point (not unique). In this paper we prove that it remains undecidable to know whether every circular configuration of a given CA evolves to the {\em same} fixed point. Our proof is based on properties concerning NW-deterministic periodic tilings of the plane. As a corollary it is concluded the (already proved) undecidability of the periodic tiling problem (nevertheless, our approach could also be used to prove this result in a direct and very simple way).
De nombreux travaux ont été consacrés à la compréhension de l'évolution à long terme des automates cellulaires (AC). Comme pour les autres types de systèmes dynamiques, cette évolution à long terme est décrite par ses attracteurs. Dans ce contexte, il a été démontré indécidable de savoir si toute configuration périodique d'un AC donné évolue vers un point fixe (peut-{\^e}tre non unique). Dans cet article, nous prouvons l'indécidabilité de savoir si toute configuration périodique evolue vers le {\em m{\^e}me} point fixe. Notre preuve s'appuie sur les propietés des pavages NW-déterministe et périodiques du plan. Comme corollaire, nous obtenons l'indécidabilité (déjà connue) de la pavabilité périodique (cependant notre approche permet d'arriver à ce résultat de fa{\c{c}}on simple et directe).
| Origine | Fichiers produits par l'(les) auteur(s) |
|---|
Loading...