# Local rule for the product of two cellular automata

Consider two one-dimensional cellular automata $$(A^{\mathbb Z},F)$$ and $$(B^{\mathbb Z},G)$$ with alphabets $$A$$ and $$B$$ and global rules $$F: A^{\mathbb Z} \to A^{\mathbb Z}$$ and $$G: B^{\mathbb Z} \to B^{\mathbb Z}$$ corresponding to the local rules $$f: A^m \to A$$ and $$g: B^n \to B$$ respectively.

Consider the product cellular automaton $$(A^{\mathbb Z} \times B^{\mathbb Z}, F \times G)$$. These kinds of products are commonly used in dynamical systems to construct interesting examples (or counterexamples).

My question: Is there a way to re-code the product cellular automaton above on a one-dimensional configuration space? That is, can we find a (somehow) equivalent cellular automaton $$(C^{\mathbb Z}, H)$$ with a global rule $$H: C^{\mathbb Z} \to C^{\mathbb Z}$$ induced by an explicit local rule $$h: C^k \to C$$ which is more convenient to study?

• Plural of automaton is automata Commented Aug 18, 2022 at 19:24
• @J.W.Tanner As the tag indicates Commented Aug 18, 2022 at 19:27
• Increase neighborhoods artificially to be equal, take $B = A\times A$, use the obvious product of local rules. Commented Aug 18, 2022 at 23:39
• The asterisk in the notation $A^Z*A^Z$ is not very clear to me. We would use the symbol $\times$ for the Cartesian product if we want to use the Cartesian product. And if we are using $Z$ to denote the integers, we would write $\mathbb{Z}$. Commented Aug 19, 2022 at 1:32
• Hi, kiki, and welcome to MathOverflow. I've edited your question to (hopefully) standardize and clarify the notation a bit, and also to generalize it slightly to allow the original automata to have distinct alphabets $A$ and $B$. I hope I haven't introduced any errors while editing; if I have, please do correct them and feel free to improve or revert any changes I've made that you may disagree with. Thanks! Commented Aug 19, 2022 at 15:09

## 1 Answer

Assuming that my edits to your question indeed reflect your intent correctly, the answer seems simple (and, indeed, was basically already sketched by Ville Salo in a comment above).

First, let's assume that the local rules $$f$$ and $$g$$ for the original cellular automata have the same neighborhood size, i.e. that $$m = n$$. (If that's not the case, you can always increase the size of the smaller neighborhood to make them equal.)

Now, we make use of the fact that the sets $$A^{\mathbb Z} \times B^{\mathbb Z}$$ and $$(A \times B)^{\mathbb Z}$$ are naturally isomorphic, with the isomorphism mapping any pair of configurations $$(x_i)_{i \in \mathbb Z} \in A^{\mathbb Z}$$ and $$(y_i)_{i \in \mathbb Z} \in B^{\mathbb Z}$$ to the configuration $$(x_i, y_i)_{i \in \mathbb Z} \in (A \times B)^{\mathbb Z}$$. (Of course, this works just as well with any index set, not just $$\mathbb Z$$.)

Thus, we can simply represent the product automaton as $$(C^{\mathbb Z}, H)$$, where the alphabet $$C = A \times B$$ of the product automaton consist of pairs of symbols $$(x, y)$$, with $$x \in A$$ and $$y \in B$$, and where the global rule $$H$$ is induced by the local rule $$h: C^n \to C$$ defined as: $$h((x_1, y_1), …, (x_n, y_n)) = (f(x_1, …, x_n), g(y_1, …, y_n)).$$

That is, to evaluate the local rule $$h$$, we take the $$n$$-letter word $$((x_1, y_1), …, (x_n, y_n)) \in C^n$$, unpack it into the words $$(x_1, …, x_n) \in A^n$$ and $$(y_1, …, y_n) \in B^n$$, pass those into $$f$$ and $$g$$ respectively and return the pair of resulting symbols.

Of course, arguably all this formalism just obscures the underlying idea, which is that the product of two cellular automata simply consists of the two automata running in parallel without interacting, and that (when the automata share the same lattice) this can be equivalently interpreted as a single CA where each cell on the lattice stores a pair of states, one for each of the original automata, and the two halves of the state pairs evolve under their respective rules without influencing each other in any way.