Skip to main content
\(\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]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)
Mathematics LibreTexts

12.1 Sizes of Rule Space and Phase Space


\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

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 finite, i.e., there are only a finite number of “universes” possible in a given CA setting. Moreover, if the space is finite, all possible configurations 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 or phase space to study the properties of all the “parallel universes.” Stephen Wolfram did such an exhaustive search for a binary CA rule space to illustrate the possible dynamics of CA [34, 46]. 

Let’s calculate how large a rule space/phase space of a given CA setting can be. Here we assume the following: 

• Dimension of space: \(D\)

 • Length of space in each dimension: \(L\)

• Radius of neighborhood: \(R\)

• Number of states for each cell: \(K\)

To calculate the number of possible rules, we first need to know the size of the neighborhood of each cell. For each dimension, the length of each side of a neighborhood is given by \(2r + 1\), including the cell itself. In a \(D\)-dimensional space, this is raised to the power of \(D\), assuming that the neighborhood is a \(D\)-dimensional (hyper)cube. So, the size (volume) of the neighborhood is given by 


Each of the \(n\) cells in a neighborhood can take one of \(k\) states. Therefore, the total number of local situations possible is given by 


Now we can calculate the number of all possible state-transition functions. A function has to map each of the m situations to one of the \(k\) states. Therefore, the number of possible mappings is given by 

\[R =k^{m}= k^{k^{n}}=k^{k^{(2r+1)^{D}}}. \label{(12.3)}\]

For example, a one-dimensional \((D = 1)\) binary \((k = 2)\) CA model with radius 1 \((r = 1)\) has \(2^{(2×1+1)^{1}} = 2^{3} = 8\) different possible situations, and thus there are \(2^{8} = 256\) state-transition functions possible in this CA universe1. This seems reasonable, but be careful— this number quickly explodes to astronomical scales for larger \(k\), \(r\), or \(D\).

Exercise 12.1

 Calculate the number of possible state-transition functions for a two-dimensional CA model with two states and Moore neighborhoods (i.e., \(r = 1\)).

Exercise 12.2

 Calculate the number of possible state-transition functions for a three-dimensional CA model with three states and 3-D Moore neighborhoods (i.e., \(r = 1\)).

 You must have faced some violently large numbers in these exercises. Various symmetry assumptions (e.g., rotational symmetries, reflectional symmetries, totalistic rules, etc.) are often adopted to reduce the size of the rule spaces of CA models. 

How about the size of the phase space? It can actually be much more manageable compared to the size of rule spaces, depending on how big \(L\) is. The total number of cells in the space (i.e., the volume of the space) is given by

Each cell in this volume takes one of the \(k\) states, so the total number of possible configurations (i.e., the size of the phase space) is simply given by 

\[S=k^{V} =k^{L^{D}}. \label{(12.5)}\]

For example,a one-dimensional binary CA model with \(L = 10\) has \(2^{10^{1}} = 1024\) possible configurations, a two-dimensional binary CA model with \(L = 10\) has \((2^{10^{2}} ≈ 1.27 × 10^{30}\) possible configurations. The latter is large, but it isn’t so huge compared to the size of the rule spaces you saw in the exercises above.

Exercise 12.3

Calculate the number of all possible configurations of a two-dimensional, three-state CA model with \(L = 100\).


1There is a well-known rule-numbering scheme for this particular setting proposed by Wolfram, but we don’t discuss it in detail in this textbook.