Skip to main content
addendum
Source Link

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.

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.

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.

deleted 15 characters in body
Source Link

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 neigborhoodneighborhood 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$-tuple of symbol pairsletter word $((x_1, y_1), …, (x_n, y_n)) \in C^n$, unpack it into two $n$-tuplesthe 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.

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 neigborhood 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$-tuple of symbol pairs $((x_1, y_1), …, (x_n, y_n)) \in C^n$, unpack it into two $n$-tuples $(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.

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.

Source Link

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 neigborhood 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$-tuple of symbol pairs $((x_1, y_1), …, (x_n, y_n)) \in C^n$, unpack it into two $n$-tuples $(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.