Although our classification is very crude, we argue that it is more objective than Wolfram’s (due to the greater ease of determining a rigorous answer to these questions), more predictive (as we can classify large groups of rules without observing them individually), and more accurate in focusing attention on rules likely to support patterns with complex behavior. If one or both of these conditions is not true, then there may still be phenomena of interest supported by the given cellular automaton rule, but we will have to look harder for them. We propose a four-way classification of two-dimensional semi-totalistic cellular automata that is different than Wolfram’s, based on two questions with yes-or-no answers: do there exist patterns that eventually escape any finite bounding box placed around them? And do there exist patterns that die out completely? If both of these conditions are true, then a cellular automaton rule is likely to support spaceships, small patterns that move and that form the building blocks of many of the more complex patterns that are known for Life. It is predicated on the assumption that interesting behavior should emerge from uninformative initial conditions, but many of the most interesting patterns in Life could not have been found in this way. Wolfram’s classification defines the interesting rules negatively rather than positively: they are the rules where some known type of uninteresting behavior doesn’t happen. When the boundary is clear, it is not where we might like it to be: for instance, the rule B35/S236 (discussed below) appears to be in Class III, but can support many complex patterns similar to those in Life. It is not obvious, even, which class Life properly belongs to, and it is conventionally classified as Class IV less because the description of that class best fits our observations of Life and more because Life is the archetypical rule whose behavior Class IV was intended to capture. Some automata may have a constant probability of behaving in more than one of these ways BalShe-TCS-00, making them difficult to classify. The boundary between classes is less clear-cut and more subjective than one would like, and may for some automata be impossible to decide McI-PD-90 CulYu-CS-88. Although there is some evidence for phase transitions between regions of rule space where one class is more frequent than others ChaMan-PD-90 LiPacLan-PD-90 WooLan-PD-90 LafBos-RAAL-05, the classification depends strongly on the specific behavior of an individual rule, so that one cannot use it to predict which rules are likely to have interesting behavior, but only to describe that behavior after having already observed it. However, Wolfram’s classification is problematic in more than one way.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |