# 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 ﬁ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 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 ﬁrst 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

\[n=(2r+1)^{D}\label{(12.1)}\]

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

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

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 universe^{1}. 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, reﬂectional 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

\[V=L^{D}.\label{(12.4)}\]

Each cell in this volume takes one of the \(k\) states, so the total number of possible conﬁgurations (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 conﬁgurations, a two-dimensional binary CA model with \(L = 10\) has \((2^{10^{2}} ≈ 1.27 × 10^{30}\) possible conﬁgurations. 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 conﬁgurations of a two-dimensional, three-state CA model with \(L = 100\).

__ __

^{1}There 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.