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

Automata with memory

There is another way to use the cartesian product to create a composite automaton. Begin with the automaton whose transition rule is . Define, for pairs such as ( is exclusive or),

The left part of the pair simply remembers the right part from the old generation while the right part combines the new and old values of the cell. Thus both items of information are always present and can be extracted if needed. The inverse rule, whose structure is similar, follows the same procedure.

States a and e are of no consequence in defining the transition, serving simply as a one-generation memory which will be forgotten by the second generation. Nevertheless their presence is essential, likewise the fact that must ignore them.

As with the cartesian product, we have a automaton with the square of the number of states and the same width. Still another way to induce an automaton in the cartesian product would be to omit the exclusive or:

from which the previous generation with respect to can always be recovered, but not with respect to . By contrast all of 's previous generations can be recovered, but it must not be thought that the same applies to , even though it participates in the definition of .

For example, suppose that , which is not reversible at all. Then , indeed reversible, but of no help whatsoever for obtaining .

Harold V. McIntosh