Next: Factor automata Up: What to look Previous: Ancestors

# Subautomata

Binary automata may be judged to be less interesting because they ``don't do anything'' or fall into Wolfram's Classes I and II; but there are other ways in which automata with larger numbers of internal states can fall into a pattern of restrictive behavior. For many rules, watching the screen display for a while will reveal that one of the colors has disappeared. This would be especially noticeable for a rule in which a certain value never appeared in the rule, because it would have to be be absent in all lines after the first.

A mathematician would describe this situation by saying that he was dealing with a subautomaton -- one for which a subset of states could be found which was closed under evolution. What that means is that states in the given subset would evolve only into each other and into no others. Just as mathematical definitions tend to include many apparent quibbles as extreme cases of some general proposition, it might be remarked that a good many automata actually exhibit one extreme example of subset behavior. For these automata dead states evolve only into dead states, using Conway's biological metaphor.

Here, the extreme subset is the one consisting of just the quiescent state, so that the subset automaton, strictly speaking, would be a monary automaton; a category which we might have thought that we would never need to use. In reality we have happened upon the concept of an automaton with a quiescent state (a more elegant adjective than ``dead''), and seen its characterization by saying that the quiescent state belonged to a subautomaton.

At the opposite extreme, equally a convenient quibble, the whole set of states can be considered as a subset of states forming its own automaton. The value of setting up such a vocabulary becomes apparent when we have more complicated automata in which a whole hierarchy of subautomata can be perceived and we want to make systematic comparisons between the members of the hierarchy.

Next: Factor automata Up: What to look Previous: Ancestors

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