next up previous contents
Next: Product automata Up: What to look Previous: Subautomata

Factor automata

There is another mathematical concept related to subsets, which is the idea of equivalence relations. According to this concept, two or more states of the automaton might be regarded as being interchangeable. If not actually identical, there is no essential difference between them. Watching the evolution of certain automata on the screen, there sometimes seems to be a wash of color laid over an underlying pattern. The pattern seems to endure, while the color overlay has a life of its own. This is an example of a factor automaton, in which the overlaid colors are equivalent. They form one equivalence class, black (the general background color) another; the automaton could just as well be binary and could be viewed on a monochromatic screen.

Finally, there are mappings from one automaton to another. One of the simplest examples would be to complement all the cells of a binary automaton. The complemented automaton would probably not evolve according to the same rules, but it might. For automata whose states are television colors, interchanging the colors would be such a mapping. Aesthetically the difference is striking; mathematically it is the same automaton.

Let f be a function between the state sets of automaton A and automaton , with equal neighborhood size and evolutionary functions and . Functions which satisfy the condition

are of a special kind, evidently more compatible with the two automata than arbitrary functions. Counterimages of individual states by such a function are the prototypes of equivalence classes; equivalence means having the same image.

Harold V. McIntosh