Paper #: 98-02-018
“Glider” dynamics in cellular automata (CA), where coherent configurations emerge and interact, provide a stark instance of self-organization in a simple system. Such behavior was classified as class 4 or complex (as opposed to ordered or chaotic) by Wolfram, and was one of the original motivations for Artificial Life. Because glider dynamics is relatively rare in CA rule spaces, much study has focused on the few known complex rules. However, a more general theory would benefit from many examples, which are now available for 1one-dimensional CA found by the methods described. Cellular automata rules can be classified automatically for a spectrum of ordered, complex, and chaotic dynamics, by a measure of the variance of input-entropy over time. The method allows screening out rules that display glider dynamics and related complex rules, giving an unlimited source for further study. The method also shows the distribution of rule classes in the rule-spaces of varying neighborhood sizes. The classification produced seems to correspond to our subjective view of space-time dynamics, and to global measures on the “bushiness” of typical sub-trees in attractor basins, characterized by the distribution of in-degree sizes in their branching structure. The paper explains the methods and presents results for one-dimensional CA.