  We numerically study the dynamics of elementary 1D cellular automata (CA),
where the binary state $\sigma_i(t) \in \{0,1\}$ of a cell $i$ does not only
depend on the states in its local neighborhood at time $t-1$, but also on the
memory of its own past states $\sigma_i(t-2),
\sigma_i(t-3),...,\sigma_i(t-\tau),...$. We assume that the weight of this
memory decays proportionally to $\tau^{-\alpha}$, with $\alpha \ge 0$ (the
limit $\alpha \to \infty$ corresponds to the usual CA). Since the memory
function is summable for $\alpha>1$ and nonsummable for $0\le \alpha \le 1$, we
expect pronounced %qualitative and quantitative changes of the dynamical
behavior near $\alpha=1$. This is precisely what our simulations exhibit,
particularly for the time evolution of the Hamming distance $H$ of initially
close trajectories. We typically expect the asymptotic behavior $H(t) \propto
t^{1/(1-q)}$, where $q$ is the entropic index associated with nonextensive
statistical mechanics. In all cases, the function $q(\alpha)$ exhibits a
sensible change at $\alpha \simeq 1$. We focus on the class II rules 61, 99 and
111. For rule 61, $q = 0$ for $0 \le \alpha \le \alpha_c \simeq 1.3$, and $q<0$
for $\alpha> \alpha_c$, whereas the opposite behavior is found for rule 111.
For rule 99, the effect of the long-range memory on the spread of damage is
quite dramatic. These facts point at a rich dynamics intimately linked to the
interplay of local lookup rules and the range of the memory. Finite size
scaling studies varying system size $N$ indicate that the range of the
power-law regime for $H(t)$ typically diverges $\propto N^z$ with $0 \le z \le
1$. Similar studies have been carried out for other rules, e.g., the famous
"universal computer" rule 110.
