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\cdot \mathcal{T}(x)=\mathcal{T}(\varphi (h)\cdot x)$, for all $x\in A^G,h\in H$, where $\cdot$ 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 $\psi$-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 $\psi$-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.

15 pages

References in corpus (1)

• A generalization of cellular automata over groups