Cellular Automata in Popular Culture - Rule Space

Rule Space

An elementary cellular automaton rule is specified by 8 bits, and all elementary cellular automaton rules can be considered to sit on the vertices of the 8-dimensional unit hypercube. This unit hypercube is the cellular automaton rule space. For next-nearest-neighbor cellular automata, a rule is specified by bits, and the cellular automaton rule space is a 32-dimensional unit hypercube. A distance between two rules can be defined by the number of steps required to move from one vertex, which represents the first rule, and another vertex, representing another rule, along the edge of the hypercube. This rule-to-rule distance is also called the Hamming distance.

Cellular automaton rule space allows us to ask the question concerning whether rules with similar dynamical behavior are ``close" to each. Graphically drawing a high dimensional hypercube on the 2-dimensional plane remains a difficult task, and one crude locator of a rule in the hypercube is the number of bit-1 in the 8-bit string for elementary rules (or 32-bit string for the next-nearest-neighbor rules). Drawing the rules in different Wolfram classes in these slices of the rule space show that class 1 rules tend to have lower number of bit-1's, thus located in one region of the space, whereas class 3 rules tend to have higher proportion (50%) of bit-1's.

For larger cellular automaton rule space, it is shown that class 4 rules are located between the class 1 and class 3 rules. This observation is the foundation for the phrase edge of chaos, and is reminiscent of the phase transition in thermodynamics.