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].
|Citazione:||Acerbi, L., Formenti, E., & Dennunzio, A. (2007). Shifting and Lifting of Cellular Automata. In Computation and Logic in the Real World, Third Conference on Computability in Europe, CiE 2007 (pp.1-10). Springer.|
|Carattere della pubblicazione:||Scientifica|
|Titolo:||Shifting and Lifting of Cellular Automata|
|Autori:||Acerbi, L; Formenti, E; Dennunzio, A|
|Data di pubblicazione:||2007|
|Nome del convegno:||Third Conference on Computability in Europe, CiE 2007|
|Appare nelle tipologie:||02 - Intervento a convegno|