Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Reports

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 metadata

Cited literature [5 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02102003
Contributor : Colette ORANGE Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 9:11:46 AM
Last modification on : Saturday, September 11, 2021 - 3:19:16 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

5

Files downloads

17