Undecidability of the global fixed point attractor problem on circular cellular automata.

Abstract : 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).
Document type :
Reports
Complete list of metadatas

Cited literature [5 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02102003
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:11:46 AM
Last modification on : Wednesday, May 8, 2019 - 1:34:27 AM

File

RR1997-34.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02102003, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

3

Files downloads

8