Elementary, finite and linear vN-regular cellular automata (Q2201792): Difference between revisions

Let \(G\) be any group and \(A\) be any set. The set of all functions from \(G\) to \(A\) is denoted by \(A^G\). Let \(\operatorname{CA}(G; A)\) be the set of all CA over \(A^G\). A cellular automaton \(\tau\in\operatorname{CA}(G; A)\) is von Neumann regular (vN-regular) if there exists \(\sigma\in\operatorname{CA}(G; A)\) such that \(\tau\sigma\tau=\tau\). In the present paper, the authors are interested in the vN-regular elements in monoids of CA. The authors present some basic results and examples, and they establish that the monoid \(\operatorname{CA}(G; A)\) is not vN-regular. The authors obtain a partial classification of the vN-regular elementary CA over \(\{0, 1\}^{\mathbb{Z}}\). The authors prove that the monoid \(\operatorname{CA}(G; A)\) is vN-regular if and only if \(|G| = 1\) or \(|A| = 1\). The authors study whether elementary cellular automata (ECAs) are vN-regular. The authors prove that rules like 128 and 254 are vN-regular, while others, like the well-known rules 90 and 110, are not vN-regular. Then, the authors study the vN-regular elements of \(\operatorname{CA}(G; A)\) when \(G\) and \(A\) are both finite; in particular, the authors characterize them and describe a vN-regular submonoid. The vN-regular elements of the monoid \(\operatorname{LCA}(G; V)\) of linear CA are studied when \(V\) is a vector space over a field \(\mathbb{F}\). Let \(G\) be torsion-free elementary amenable (e.g., \(G =\mathbb{Z}^d\)), under some conditions the authors prove that \(\tau \in \operatorname{LCA}(G; \mathbb{F})\) is vN-regular if and only if it is invertible.