Lazy and invertible cellular automata do not generate all cellular automata

Abstract

Over the Klein four-group with the binary alphabet, the cellular automaton that complements the configurations with exactly one cell equal to 1 and fixes all others is not a finite composition of invertible and lazy cellular automata. This answers Problem 2 of E. Alcala-Arroyo and A. Castillo-Ramirez (arXiv:2510.14841) negatively: the invertible and the lazy cellular automata do not generate the monoid of all cellular automata.

Definition 1.1 (Cellular automata).

$$\mathrm{IsCA}\left(T\right)\iff (\exists S\in \mathrm{Finset}\left(G\right),mu:A^S\to A,\forall x\in A^G,g\in G,T\left(x\right)\left(g\right)=mu\left(s\mapsto x\left(s\cdot g\right)\right))$$

Formalization. D5/S3/StatisticalMechanics/CellularAutomata/LazyInvertibleGeneration.IsCA (✓ std3).

Citation. Edgar Alcalá-Arroyo; Alonso Castillo-Ramirez (2025). On the order of lazy cellular automata. DOI: 10.1016/j.tcs.2026.115965. URL: https://arxiv.org/abs/2510.14841v3.

Commentary.

For a group G and an alphabet A, a map T from A^G to itself is a cellular automaton when there are a finite neighborhood S of G (an element of Finset(G)) and a local map mu from A^S to A with T(x)(g) = mu(s -> x(s g)) for every configuration x and every g in G, that is, mu applied to the restriction to S of the shifted configuration (g . x)(h) = x(h g).

Definition 1.2 (Lazy cellular automata).

$$\mathrm{IsLazy}\left(T\right)\iff (\exists S\in \mathrm{Finset}\left(G\right),e\in S,mu:A^S\to A,p\in A^S,(\forall z\in A^S,mu\left(z\right)=z\left(e\right)\iff z\ne p)\wedge (\forall x\in A^G,g\in G,T\left(x\right)\left(g\right)=mu\left(s\mapsto x\left(s\cdot g\right)\right)))$$

Formalization. D5/S3/StatisticalMechanics/CellularAutomata/LazyInvertibleGeneration.IsLazy (✓ std3).

Citation. Edgar Alcalá-Arroyo; Alonso Castillo-Ramirez (2025). On the order of lazy cellular automata. DOI: 10.1016/j.tcs.2026.115965. URL: https://arxiv.org/abs/2510.14841v3.

Commentary.

A cellular automaton is lazy when it has a local map mu on a finite neighborhood S containing the identity e and a pattern p in A^S such that mu(z) = z(e) holds exactly for the patterns z different from p: the automaton keeps every cell except where the pattern p occurs, and there it writes the symbol mu(p), which differs from p(e).

Definition 1.3 (Invertible cellular automata).

$$\mathrm{IsInvertibleCA}\left(T\right)\iff ((\mathrm{IsCA}\left(T\right))\wedge (\exists T^{\prime },(\mathrm{IsCA}\left(T^{\prime }\right))\wedge ((T^{\prime }\cdot T=1)\wedge (T\cdot T^{\prime }=1))))$$

Formalization. D5/S3/StatisticalMechanics/CellularAutomata/LazyInvertibleGeneration.IsInvertibleCA (✓ std3).

Citation. Edgar Alcalá-Arroyo; Alonso Castillo-Ramirez (2025). On the order of lazy cellular automata. DOI: 10.1016/j.tcs.2026.115965. URL: https://arxiv.org/abs/2510.14841v3.

Commentary.

A cellular automaton T is invertible when some cellular automaton T’ satisfies T’ T = 1 and T T’ = 1 in the monoid of maps of A^G under composition.

Definition 1.4 (Problem 2).

$$claim\iff (\forall G,A,(((\mathrm{Group}\left(G\right))\wedge (\mathrm{Finite}\left(A\right)))\wedge (\mathrm{Nontrivial}\left(A\right)))\Rightarrow \forall T:A^G\to A^G,(\mathrm{IsCA}\left(T\right))\Rightarrow T\in ⟨\{U:\mathrm{IsInvertibleCA}\left(U\right)\}\cup \{U:\mathrm{IsLazy}\left(U\right)\}⟩)$$

Formalization. D5/S3/StatisticalMechanics/CellularAutomata/LazyInvertibleGeneration.claim (✓ std3).

Citation. Edgar Alcalá-Arroyo; Alonso Castillo-Ramirez (2025). On the order of lazy cellular automata. DOI: 10.1016/j.tcs.2026.115965. URL: https://arxiv.org/abs/2510.14841v3.

Commentary.

The equality asked in Problem 2, written as a universal statement: for every group G and every finite alphabet A with at least two symbols (a nontrivial type), every cellular automaton over A^G belongs to the submonoid generated by the invertible and the lazy cellular automata, that is, it is a finite composition of such automata. The theorem below shows that this statement is false.

Theorem 1.5 (A cellular automaton that is not generated).

$$\neg claim$$

Proof. Machine-checked in Lean as D5/S3/StatisticalMechanics/CellularAutomata/LazyInvertibleGeneration.result (✓ std3). ∎

Resolves. Problems/alcala-arroyo-2025-lazy-invertible-generation (refuted) by D5/S3/StatisticalMechanics/CellularAutomata/LazyInvertibleGeneration.result.

Source. Repository-derived.

Acknowledgement. Edgar Alcalá-Arroyo; Alonso Castillo-Ramirez (2025). On the order of lazy cellular automata. DOI: 10.1016/j.tcs.2026.115965. URL: https://arxiv.org/abs/2510.14841v3.

Commentary.

Let G be the Klein four-group and A = {0, 1}, let w(x) be the number of cells of x equal to 1, and let F complement x when w(x) = 1 and fix x otherwise; F is a cellular automaton with neighborhood G because w is invariant under the shifts. Every cellular automaton commutes with the shifts. In the Klein four-group every configuration of even weight is fixed by a shift by some k different from e, since a support {u, v} is fixed by k = u^(-1) v, and every configuration fixed by such a shift has even weight, being a union of cosets of {e, k}; hence a cellular automaton sends even weight to even weight, and it sends the two constant configurations to constant configurations. A lazy automaton whose pattern p is constant equal to b sends both constant configurations to the constant 1 - b. If p is not constant, it has a cell s with p(s) = 1, and in a configuration with a single cell u equal to 1 the pattern can occur only at the position s^(-1) u; with a cell where p is 0 the same holds for weight three, so on a configuration of odd weight the lazy automaton changes at most one cell, and its image is either the configuration itself or of even weight. Consider the property of a cellular automaton T: if T separates the two constant configurations, then T is injective on the configurations of odd weight whose image has odd weight. Invertible automata have it because they are injective, lazy automata have it by the previous step, and it is preserved under composition: a composition that separates the constants has a first factor that permutes the two constants and a second factor that separates them, and a configuration whose final image has odd weight has odd weight at every intermediate stage. So every element of the generated submonoid has the property. But F separates the constants and sends both the configuration with the single 1 at e and its complement, of weight three, to that complement.

References

• Truth anchor: D5/S3/StatisticalMechanics/CellularAutomata/LazyInvertibleGeneration.IsCA
• Truth anchor: D5/S3/StatisticalMechanics/CellularAutomata/LazyInvertibleGeneration.IsInvertibleCA
• Truth anchor: D5/S3/StatisticalMechanics/CellularAutomata/LazyInvertibleGeneration.IsLazy
• Truth anchor: D5/S3/StatisticalMechanics/CellularAutomata/LazyInvertibleGeneration.claim
• Truth anchor: D5/S3/StatisticalMechanics/CellularAutomata/LazyInvertibleGeneration.result