Elementary, finite and linear vN-regular cellular automata

Castillo-Ramirez, Alonso; Gadouleau, Maximilien

Abstract

Let G be a group and A a set. A cellular automaton (CA) over AG is von Neumann regular (vN-regular) if there exists a CA over AG such that = , and in such case, is called a weak generalised inverse of . In this paper, we investigate vN-regularity of various kinds of CA. First, we establish that, over any nontrivial conguration space, there always exist CA that are not vN-regular. Then, we obtain a partial classication of elementary vN-regular CA over f0; 1gZ; in particular, we show that rules like 128 and 254 are vN-regular (and actually generalised inverses of each other), while others, like the well-known rules 90 and 110, are not vN-regular. Next, when A and G are both nite, we obtain a full characterisation of vN-regular CA over AG. Finally, we study vN-regular linear CA when A = V is a vector space over a eld F; we show that every vN-regular linear CA is invertible when V = F and G is torsion-free elementary amenable (e.g. when G = Zd; d 2 N), and that every linear CA is vN-regular when V is nite-dimensional and G is locally nite with char(F) - o(g) for all g 2 G.

Citation

Castillo-Ramirez, A., & Gadouleau, M. (2020). Elementary, finite and linear vN-regular cellular automata. Information and Computation, 274, Article 104533. https://doi.org/10.1016/j.ic.2020.104533

• Journal Article Type: Article
• Online Publication Date: Mar 2, 2020
• Publication Date: Oct 2, 2020
• Deposit Date: Mar 3, 2020
• Publicly Available Date: Mar 2, 2021
• Journal: Information and Computation
• Print ISSN: 0890-5401
• Electronic ISSN: 1090-2651
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 274
• Article Number: 104533
• DOI: https://doi.org/10.1016/j.ic.2020.104533
• Public URL: https://durham-repository.worktribe.com/output/1269183