On the order of lazy cellular automata
This work addresses a theoretical problem in cellular automata theory, focusing on incremental analysis of dynamical behavior for researchers in discrete mathematics and theoretical computer science.
The paper tackles the problem of determining the order of lazy cellular automata over arbitrary groups, establishing a general upper bound based on the fibers of the active transition and proving it is attained for quasi-constant patterns.
We study the most elementary family of cellular automata defined over an arbitrary group universe $G$ and an alphabet $A$: the lazy cellular automata, which act as the identity on configurations in $A^G$, except when they read a unique active transition $p \in A^S$, in which case they write a fixed symbol $a \in A$. As expected, the dynamical behavior of lazy cellular automata is relatively simple, yet subtle questions arise since they completely depend on the choice of $p$ and $a$. In this paper, we investigate the order of a lazy cellular automaton $τ: A^G \to A^G$, defined as the cardinality of the set $\{ τ^k : k \in \mathbb{N} \}$. In particular, we establish a general upper bound for the order of $τ$ in terms of the fibers of $p$, and we prove that this bound is attained when $p$ is a quasi-constant pattern.