On the order of lazy cellular automata

Abstract

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 $\tau :A^G\to A^G$, defined as the cardinality of the set $\{{\tau }^k:k\in \mathbb{N}\}$. In particular, we establish a general upper bound for the order of $\tau$ in terms of the fibers of $p$, and we prove that this bound is attained when $p$ is a quasi-constant pattern.

arXiv comment14 pages

References in corpus (1)

• Idempotent cellular automata and their natural order