Undecidability of the global fixed point attractor problem on circular cellular automata. - LARA - Libre accès aux rapports scientifiques et techniques Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1997

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).
Fichier principal
Vignette du fichier
RR1997-34.pdf (238.35 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02102003 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02102003 , version 1

Citer

Jacques Mazoyer, Ivan Rapaport. Undecidability of the global fixed point attractor problem on circular cellular automata.. [Research Report] LIP RR-1997-34, Laboratoire de l'informatique du parallélisme. 1997, 2+14p. ⟨hal-02102003⟩
13 Consultations
28 Téléchargements

Partager

Gmail Facebook X LinkedIn More