Global fixed point attractors of circular cellular automata and periodic tilings of the plane: Undecidability results
| Autor: | Ivan Rapaport, Jacques Mazoyer |
|---|---|
| Rok vydání: | 1999 |
| Předmět: |
Discrete mathematics
Plane (geometry) Fixed point attractors Context (language use) Fixed point Undecidability Cellular automaton Undecidable problem Theoretical Computer Science Combinatorics Simple (abstract algebra) Attractor Periodic tilings of the plane Discrete Mathematics and Combinatorics Dynamical system (definition) Circular cellular automata Mathematics |
| Zdroj: | Discrete Mathematics. 199(1-3):103-122 |
| ISSN: | 0012-365X |
| DOI: | 10.1016/s0012-365x(98)00203-9 |
| Popis: | A great amount of work has been deveted 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 whether every circular configuration of a given CA evolves to some fixed point (not unique). In this paper we prove that it remains undecidable whether every circular configuration of a given CA evolves to the 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect