$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 12: Cellular Automata II - Analysis

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

• 12.1: Sizes of Rule Space and Phase Space
One of the unique features of typical CA models is that time, space, and states of cells are all discrete. Because of such discreteness, the number of all possible state-transition functions is ﬁnite, i.e., there are only a ﬁnite number of “universes” possible in a given CA setting. Moreover, if the space is ﬁnite, all possible conﬁgurations of the entire system are also enumerable. This means that, for reasonably small CA settings, one can conduct an exhaustive search of the entire rule space o
• 12.2: Phase Space Visualization
If the phase space of a CA model is not too large, you can visualize it using the technique we discussed in Section 5.4. Such visualizations are helpful for understanding the overall dynamics of the system, especially by measuring the number of separate basins of attraction, their sizes, and the properties of the attractors.
• 12.3: Mean-Field Approximation
Behaviors of CA models are complex and highly nonlinear, so it isn’t easy to analyze their dynamics in a mathematically elegant way. But still, there are some analytical methods available. Mean-ﬁeld approximation is one such analytical method. It is a powerful analytical method to make a rough prediction of the macroscopic behavior of a complex system.
• 12.4: Renormalization Group Analysis to Predict Percolation Thresholds
The next analytical method is for studying critical thresholds for percolation to occur in spatial contact processes, like those in the epidemic/forest ﬁre CA model discussed in Section 11.5. The percolation threshold may be estimated analytically by a method called renormalization group analysis.