Categorical products of cellular automata

Abstract

We study two categories of cellular automata. First, for any group $G$, we consider the category $\mathcal{C}\mathcal{A}(G)$ whose objects are configuration spaces of the form $A^G$, where $A$ is a set, and whose morphisms are cellular automata of the form $\tau :A_1^G\to A_2^G$. We prove that the categorical product of two configuration spaces $A_1^G$ and $A_2^G$ in $\mathcal{C}\mathcal{A}(G)$ is the configuration space $(A_1\times A_2{)}^G$. Then, we consider the category of generalized cellular automata $\mathcal{G}\mathcal{C}\mathcal{A}$, whose objects are configuration spaces of the form $A^G$, where $A$ is a set and $G$ is a group, and whose morphisms are $\varphi$-cellular automata of the form $\mathcal{T}:A_1^{G_1}\to A_2^{G_2}$, where $\varphi :G_2\to G_1$ is a group homomorphism. We prove that a categorical weak product of two configuration spaces $A_1^{G_1}$ and $A_2^{G_2}$ in $\mathcal{G}\mathcal{C}\mathcal{A}$ is the configuration space $(A_1\times A_2{)}^{G_1\ast G_2}$, where $G_1\ast G_2$ is the free product of $G_1$ and $G_2$. The previous results allow us to naturally define the product of two cellular automata in $\mathcal{C}\mathcal{A}(G)$ and the weak product of two generalized cellular automata in $\mathcal{G}\mathcal{C}\mathcal{A}$.

10 pages