next up previous contents
Next: Reversible automata Up: The automaton itself Previous: The automaton itself

Cartesian product

In turn, four is the smallest number of states allowing the exploration of a non-trivial state space, namely the cartesian product of two binary state spaces. Aside from the classical cartesian product, in which the two factors evolve independently, other combinations are possible, including Fredkin's construction of reversible automata.

Suppose that there is some one dimensional automaton A whose evolution follows the function , and a second, B, whose rule is . Then their cartesian product is another automaton whose states are cartesian products of the states of A with those of B, having the rule of evolution

To provide a similar definition for two-dimensional automata requires no more than extending each function to four variables rather than two, the same as needs to be done for any other dimension or neighborhood structure.

Every pair of binary rules leads to a distinct quaternary automaton, but even so, the number of quaternary rules which are cartesian products is a very small fraction of the total number of rules.



Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx