Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
435491 | Theoretical Computer Science | 2009 | 9 Pages |
We consider the family of all the Cellular Automata (CA) sharing the same local rule but having different memories. This family contains also all CA with memory m≤0 (one-sided CA) which can act both on AZ and on AN. We study several set theoretical and topological properties for these classes. In particular, we investigate whether the properties of a given CA are preserved when considering the CA obtained by changing the memory of the original one (shifting operation). Furthermore, we focus our attention on the one-sided CA acting on AZ, starting from the one-sided CA acting on AN and having the same local rule (lifting operation). As a particular consequence of these investigations, we prove that the long-standing conjecture [Surjectivity ⇒ Dense Periodic Orbits (DPO)] can be restated in several different (but equivalent) ways. Furthermore, we give some results on properties conserved under the iteration of the CA global map.