Abstract
We consider the family of all the Cellular Automata (CA) sharing the same local rule but have different memory. This family contains also all the CA with memory m ≤ 0 (one-sided CA) which can act both on A ℤ and on A ℕ. We study several set theoretical and topological properties for these classes. In particular we investigate if the properties of a given CA are preserved when we consider the CA obtained by changing the memory of the original one (shifting operation). Furthermore we focus our attention to the one-sided CA acting on A ℤ starting from the one-sided CA acting on A ℕ and having the same local rule (lifting operation). As a particular consequence of these investigations, we prove that the long-standing conjecture [Surjectivity ⇒ Density of the Periodic Orbits (DPO)] is equivalent to the conjecture [Topological Mixing ⇒ DPO].
| Original language | English |
|---|---|
| Title of host publication | COMPUTATION AND LOGIC IN THE REAL WORLD, PROCEEDINGS |
| Editors | SB Cooper, B Lowe, A Sorbi |
| Number of pages | 10 |
| Publisher | Springer-Verlag |
| Publication date | 2007 |
| Pages | 1-10 |
| ISBN (Print) | 978-3-540-73000-2 |
| Publication status | Published - 2007 |
| Externally published | Yes |
| MoE publication type | A4 Article in conference proceedings |
| Event | 3rd Conference on Computability in Europe (CiE 2007) - Siena, Italy Duration: 18 Jun 2007 → 23 Jun 2007 |
Publication series
| Name | Lecture Notes in Computer Science |
|---|---|
| Publisher | SPRINGER-VERLAG BERLIN |
| Volume | 4497 |
| ISSN (Print) | 0302-9743 |
Fields of Science
- discrete time dynamical systems
- cellular automata
- topological dynamics
- deterministic chaos
- EQUICONTINUITY
- POINTS