Article ID Journal Published Year Pages File Type
435491 Theoretical Computer Science 2009 9 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics