Complex Systems

The Structure of the Elementary Cellular Automata Rule Space Download PDF

Wentian Li
Santa Fe Institute, 1120 Canyon Road, Santa Fe, NM 87501, USA

Norman Packard
Center for Complex Systems Research, Physics Department, Beckman Institute,
University of Illinois, Urbana, IL 61801, USA


The structure of the elementary cellular automata rule space is investigated. The probabilities for a rule to be connected to other rules in the same class (intra-class), as well as rules in different classes (inter-class), are determined. The intra-class connection probabilities vary from around 0.3 to 0.5, an indication of the strong tendency for rules with the similar behavior to be next to each other. Rules are also grouped according to the mean-field descriptions. The mean-field clusters are classified into three classes (nonlinear, linear, and inversely linear) according to the "hot bits" in the rule table. It is shown that such classification provides another easy way to describe the rule space.