Probabilistic Induction of Cellular Automata Rules:
II. Probing CA Rule Space
Burton Voorhees, Rhyan Arthur, and Todd Keeler
In an earlier paper a probabilistic induction algorithm was introduced that allows unbiased best guess estimates of elementary cellular automata rules generating a time series of m-digit binary strings. If the time series was generated by a cellular automaton, the algorithm returns, with high probability, a rule from an equivalence class of rules that contains the generating rule. It is subject to type 1 errors, however: if the time series is random the algorithm still predicts a rule, or small set of rules as the likely generators. In the present paper, this effect is used as a probe of internal structure in the elementary cellular automata rule space. This rule space is partitioned into 42 equivalence classes and the frequencies of occurrence of rules in each class as predicted generator of random time series is determined over a large number of experimental runs. The non-random distribution that results illustrates relations between rules ,determined in terms of their predecessor profiles. Of particular interest are cases in which the algorithm does not return a single rule as winning prediction, but instead falls into an apparently stable pattern where a small set of rules are predicted with certain frequencies. These are called face off situations, and an analysis of the conditions for their stability is given.