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

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)\ne \mathrm{CA}(G;A)$ whenever $A$ is infinite or $G$ has an element of infinite order. Moreover, if $|A|=2$ and $G$ has a quotient isomorphic to the Klein four-group $C_2\times C_2$, then $M(G;A)\ne \mathrm{CA}(G;A)$. For locally finite $G$, and in particular for finite $G$, these are the only obstructions: we prove that $M(G;A)=\mathrm{CA}(G;A)$ if and only if $3\le |A|<\infty$, or $|A|=2$ and $G$ has no quotient isomorphic to $C_2\times C_2$.

arXiv comment16 pages