Further results on generalized cellular automata

Abstract

Given a finite set A and a group homomorphism $\varphi :H\to G$, a $\varphi$-cellular automaton is a function $\mathcal{T}:A^G\to A^H$ that is continuous with respect to the prodiscrete topologies and $\varphi$-equivariant in the sense that $h·\mathcal{T}(x)=\mathcal{T}(\varphi (h)·x)$, for all $x\in A^G,h\in H$, where $·$ denotes the shift actions of G and H on A ^G and A^H, respectively. When G = H and $\varphi =\text{id}$, the definition of $\text{id}$-cellular automata coincides with the classical definition of cellular automata. The purpose of this paper is to expand the theory of $\varphi$-cellular automata by focusing on the differences and similarities with their classical counterparts. After discussing some basic results, we introduce the following definition: a $\varphi$-cellular automaton $\mathcal{T}:A^G\to A^H$ has the unique homomorphism property (UHP) if $\mathcal{T}$ is not ψ-equivariant for any group homomorphism $\psi :H\to G,\psi \ne \varphi$. We show that if the difference set $\Delta (\varphi ,\psi )$ is infinite, then $\mathcal{T}$ is not ψ-equivariant; it follows that when G is torsion-free abelian, every non-constant $\mathcal{T}$ has the UHP. Furthermore, inspired by the theory of classical cellular automata, we study $\varphi$-cellular automata over quotient groups, as well as their restriction and induction to subgroups and supergroups, respectively.

KEYWORDS:

• Cellular automata
• group homomorphism
• quotient group
• restriction and induction

2020 MATHEMATICS SUBJECT CLASSIFICATION:

• 37B15
• 68Q80

Acknowledgments

We sincerely thank the anonymous reviewer of this paper for their careful reading and insightful comments; in particular, they greatly simplified the proof of Lemma 8.

Additional information

Funding

The second author was supported by a CONAHCYT Postdoctoral Fellowship Estancias Posdoctorales por México, No. I1200/320/2022.