Counting Short Trajectories in Elementary Cellular Automata using the Transfer Matrix Method
This provides a quantitative framework for understanding cellular automata behaviors, though it is incremental as it adapts an existing method to a specific domain.
The authors tackled the problem of quantifying global dynamics in Elementary Cellular Automata by developing a method to compute the exact number of configurations leading to short attractors in the thermodynamic limit, revealing that entropy varies systematically with Wolfram's classification: Class 1 and 2 rules approach maximal entropy quickly, while Class 3 and 4 rules show low or finite entropy.
Elementary Cellular Automata (ECAs) exhibit diverse behaviours often categorized by Wolfram's qualitative classification. To provide a quantitative basis for understanding these behaviours, we investigate the global dynamics of such automata and we describe a method that allows us to compute the number of all configurations leading to short attractors in a limited number of time steps. This computation yields exact results in the thermodynamic limit (as the CA grid size grows to infinity), and is based on the Transfer Matrix Method (TMM) that we adapt for our purposes. Specifically, given two parameters $(p, c)$ we are able to compute the entropy of all initial configurations converging to an attractor of size $c$ after $p$ time-steps. By calculating such statistics for various ECA rules, we establish a quantitative connection between the entropy and the qualitative Wolfram classification scheme. Class 1 rules rapidly converge to maximal entropy for stationary states ($c=1$) as $p$ increases. Class 2 rules also approach maximal entropy quickly for appropriate cycle lengths $c$, potentially requiring consideration of translations. Class 3 rules exhibit zero or low finite entropy that saturates after a short transient. Class 4 rules show finite positive entropy, similar to some Class 3 rules. This method provides a precise framework for quantifying trajectory statistics, although its exponential computational cost in $p+c$ restricts practical analysis to short trajectories.