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

@misc{alcalaarroyo2026when,
  title = {{When do lazy and invertible cellular automata generate all cellular automata?}},
  author = {Edgar Alcalá-Arroyo and Alonso Castillo-Ramirez},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.18480},
  eprint = {2610.18480},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.18480},
}

TY  - UNPB
TI  - When do lazy and invertible cellular automata generate all cellular automata?
AU  - Edgar Alcalá-Arroyo
AU  - Alonso Castillo-Ramirez
PY  - 2026
DA  - 2026/10/13
PB  - arXiv
DO  - 10.48550/arxiv.2610.18480
UR  - https://arxiv.org/abs/2610.18480
AB  - 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 CA(G;A) generated by the lazy and the invertible cellular automata. We study when M(G;A) = CA(G;A). Since no lazy cellular automaton is surjective, every surjective element of M(G;A) is invertible; hence M(G;A) ≠ 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 × C_2, then M(G;A) ≠ CA(G;A). For locally finite G, and in particular for finite G, these are the only obstructions: we prove that M(G;A) = CA(G;A) if and only if 3 ≤ |A| < ∞, or |A| = 2 and G has no quotient isomorphic to C_2 × C_2.
ER  -