Complex Systems

Partitioning of Cellular Automata Rule Spaces Download PDF

Rodrigo A. Obando
TSYS School of Computer Science
Columbus State University
4225 University Avenue
Columbus, GA 31907, USA
Obando_Rodrigo@ColumbusState.edu

Abstract

Even though cellular automata rules are simple and deterministic, there has been no way to know the class of behavior from the rule itself until it is evolved. This is not a real problem in the elementary rule space, since there is a relatively small number of rules in it. An extensive survey of their behavior has been done already. The problem arises when the neighborhood is expanded, such as for r=2, where the number of rules becomes 232 and an exhausting analysis becomes extremely time consuming. This problem is aggravated even more for k=3 and r=1, where the number of rules is 327. A partition of the rule space is presented based on new parameters and , along with the primitives and and the Gray code permutation. This partition helps identify regions of similar global behavior in the rule space. The approach is illustrated for k=2 and integer r, but it should be able to be extended to other values.