One-dimensional cellular automata with random rules: longest temporal period of a periodic solution

Abstract

We study one-dimensional cellular automata whose rules are chosen at random from among $r$-neighbor rules with a large number $n$ of states. Our main focus is the asymptotic behavior, as $n\to \infty$, of the longest temporal period $X_{\sigma ,n}$ of a periodic solution with a given spatial period $\sigma$. We prove, when $\sigma \le r$, that this random variable is of order $n^{\sigma /2}$, in that $X_{\sigma ,n}/n^{\sigma /2}$ converges to a nontrivial distribution. For the case $\sigma >r$, we present empirical evidence in support of the conjecture that the same result holds.