Paperlane

no. 7 · Tuesday 3 November 2026

When do lazy and invertible cellular automata generate all cellular automata?

Edgar Alcalá-Arroyo and Alonso Castillo-Ramirez

math.GR · v2 · 15 pp

Abstract

Let $G$ be a group and let $A$ be a set with at least two elements. A lazy cellular automaton over $A^G$ acts as the identity except at the cells where a fixed pattern occurs, where it replaces the central symbol by a fixed different symbol. Let $M(G;A)$ be the submonoid of $\mathrm{CA}(G;A)$ generated by the lazy and the invertible cellular automata. We study when $M(G;A) = \mathrm{CA}(G;A)$. Since no lazy cellular automaton is surjective, every surjective element of $M(G;A)$ is invertible; hence $M(G;A) \neq \mathrm{CA}(G;A)$ whenever $A$ is infinite or $G$ has an element of infinite order. More unexpectedly, if $|A| = 2$ and $G$ has a quotient isomorphic to the Klein four-group $C_2 \times C_2$, then $M(G;A) \neq \mathrm{CA}(G;A)$. For locally finite groups, these are the only obstructions: we prove that $M(G;A) = \mathrm{CA}(G;A)$ if and only if $3 \leq |A| < \infty$, or $|A| = 2$ and $G$ has no quotient isomorphic to $C_2 \times C_2$.

comments
15 pages
fields
Group Theory, Dynamical Systems
pdf ↗ page arXiv:2610.18480 ↗