Statistical Complexity Measures for Cellular Automata Dynamics

Povzetek

Elementary cellular automata are among the simplest systems known to generate structure spanning the full range
from trivial order to apparent randomness, yet Wolfram's original four-class behavioral taxonomy is qualitative and
does not by itself quantify how much intrinsic computation a given rule performs. We applied
computational-mechanics-based statistical complexity measures, epsilon-machine reconstruction, Shannon entropy
rate, and excess entropy, to spatial configurations generated by all 88 topologically distinct elementary cellular
automaton rules, each run from 500 random initial conditions on a 400-cell periodic lattice for 2000 time steps, with
the final 200 steps used for statistical estimation after transients were discarded. Statistical complexity, measured in
bits as the Shannon entropy of the reconstructed causal-state distribution, ranged from 0 bits for Wolfram Class I
(fixed-point) rules to a maximum of 3.42 bits for rule 110, a known Class IV (complex/computationally universal)
rule, with Class IV rules showing significantly higher mean statistical complexity (2.71 +/- 0.58 bits) than Class II
periodic rules (0.94 +/- 0.41 bits, p < 0.001, Mann-Whitney U test). Excess entropy and statistical complexity were
strongly correlated across all 88 rules (r = 0.87, p < 0.001), but a subset of 9 rules, all Class IV, showed excess
entropy at least 30% higher than predicted by the pooled linear fit, indicating memory structure not fully captured by
a single scalar entropy-rate measure. Entropy rate alone poorly discriminated Class III (chaotic) from Class IV
(complex) rules, with substantial overlap in the two classes' entropy-rate distributions (Class III: 0.81 +/- 0.15
bits/site; Class IV: 0.74 +/- 0.19 bits/site; not significantly different, p = 0.21), whereas statistical complexity
separated the two classes cleanly, with only 2 of 41 Class III rules exceeding the 10th percentile of the Class IV
statistical-complexity distribution. Reconstructed causal-state counts ranged from 1 (Class I) to 34 (rule 110), and a
sensitivity analysis varying reconstruction history length from 4 to 10 cells showed statistical complexity estimates
stabilizing to within 4% of their asymptotic value by history length 8 for 84 of the 88 rules. These results indicate that
statistical complexity, unlike entropy rate alone, provides a quantitative measure that tracks Wolfram's qualitative
Class IV designation closely, supporting its use as an automated screening criterion for identifying candidate
complex, computationally interesting cellular automaton rules.