A directed graph allowing for the exploration of the set of number-conserving non-uniform one-dimensional binary cellular automata with radius one and half
Authors:
Barbara Wolnik, Maciej Dziemiańczuk, Bartosz Makuracki, Bernard De Baets
The article delves into the intricate world of number-conserving non-uniform one-dimensional binary cellular automata with a radius of one and half, a topic that has garnered significant attention due to its ability to model complex dynamics with simple concepts. The study builds upon previous research that characterized number-conserving elementary cellular automata, extending the investigation to a more complex neighborhood size. A key contribution is the construction of a directed graph that establishes a one-to-one correspondence between the set of all number-conserving non-uniform cellular automata and the set of all length-n closed directed walks in the graph. This innovative approach allows for a comprehensive exploration of these automata, regardless of the grid length, and provides a foundation for answering fundamental questions about the impact of neighborhood size on number conservation. The article also highlights the challenges and complexities involved in studying these automata, offering a glimpse into the rich and unexplored terrain of non-uniform cellular automata.
AI Generated
This summary of the content was generated with the help of AI.
Abstract
The main obstacle in the quest for non-uniform cellular automata that meet the often desired property of number conservation is the vast size of the search space, going far beyond the capabilities of today’s computers. In this paper, we expound the construction of a directed graph \(\Pi \) related to the set of all number-conserving non-uniform one-dimensional binary cellular automata with radius one and half (i.e., the neighborhood of a cell consists of four cells). We show that there is a one-to-one correspondence between the set of all such cellular automata on a finite grid with n cells and the set of all length-n closed directed walks in \(\Pi \). This provides us with a powerful tool to investigate non-uniform cellular automata of this type.
Notes
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
1 Introduction
Cellular automata (CAs) owe their popularity to an unusual combination of two features: on the one hand, they are defined by very simple concepts; on the other hand, they are able to model all sorts of phenomena even with very complex dynamics.
The first definition of a CA, put forward by Ulam and von Neumann, assumes that each cell of some regular grid is equipped with an identical finite automaton (Ulam 1962; von Neumann 1966). However, in recent years, in an effort to enable more realistic modeling of natural systems, in which different units or parts of a system often behave differently, the concept of non-uniform CAs is receiving increased attention. In a non-uniform CA, each single cell is allowed to have its own local updating rule (see, e.g., Pries et al. 1986). Dennunzio et al. provided several examples supporting the need to go beyond uniformity (Dennunzio et al. 2012).
Advertisement
Any researcher dealing with classical (uniform) CAs knows that even the smallest increase (by one) in the size of the considered set of states, the size of the neighborhood, or the dimension of the cell space, leads to a gigantic (doubly exponential) increase in the complexity of the problem. In the case of non-uniform CAs, the situation is even much worse. For this reason, the study of non-uniform CAs is most often limited to the so-called non-uniform elementary CAs (ECAs), in which each cell is allowed to have its own local updating rule belonging to Wolfram’s set of 256 elementary local rules (see, e.g., Hortensius et al. 1989; Sipper and Tomassini 1996). Of course, several articles introduce more general definitions, such as the case where the cells may use different rules with different neighborhood sizes (Dennunzio et al. 2012; Cattaneo et al. 2009; Salo 2014). However, the non-uniform ECAs remain the primary focus in this research direction.
As for the non-uniform ECAs, their best-researched property is probably number conservation. In the uniform case, the characterization of the number conservation of ECAs turned out to be very simple. Indeed, one can use, for example, the necessary and sufficient conditions given by Boccara and Fukś to infer that there are only five number-conserving ECAs (Boccara and Fukś 1998). It is also possible to simply examine each Wolfram rule separately, as there are only 256 of them (see, e.g., Wolfram 1984). The characterization of the number conservation of non-uniform ECAs was a much more complex task. First of all, Dennunzio et al. provided an important example demonstrating that the number conservation property can sometimes be the result of “cooperation" between rules that when considered separately as local rules of a uniform CA might not be number-conserving (Dennunzio et al. 2013). Moreover, considering, for example, a grid of 10 cells, we get as many as \(256^{10}\) possible non-uniform ECAs, so it is impossible to examine each one individually to see if it is number-conserving or not. Nevertheless, the task has been completely solved, and looking at the history of this investigation, three important steps can be identified. First, Hazari and Das proved that only nine Wolfram rules can jointly form non-uniform ECAs (Hazari and Das 2016). Next, Pal et al. presented a few very interesting results obtained on the basis of computer simulations (Pal et al. 2021). Finally, Wolnik et al. gave a detailed characterization of all number-conserving non-uniform ECAs, both on finite grids (Wolnik et al. 2023a) and on infinite grids (Wolnik et al. 2023b).
In this paper, we initiate an investigation into the generalization of the problem solved in Wolnik et al. (2023a) by increasing the neighborhood size to four cells (note that we adopt the convention that each cell sees one neighbor on the left and two neighbors on the right). In other words, we want to get closer to answering the question of what all number-conserving non-uniform one-dimensional binary CAs with radius one and half look like. We focus on CAs on finite grids with periodic boundary conditions. To get a feeling for the level of complexity of this problem, let us note that on a grid of length n, as many as \((2^{16})^n = (65\, 536)^n\) different such non-uniform CAs can be defined. In addition, as shown by the experience gained in Wolnik et al. (2023a), the study should concentrate on grids with a length of at least \(n=7\). So the number of possible rules to be checked on the smallest reasonable grid is as many as the astronomical number \((65\, 536)^7\approx 5.2\cdot 10^{33}\).
The main result of this paper is the construction of a directed graph \(\Pi \), having only \(273\, 538\) vertices, with the following property: there is a one-to-one correspondence between the set of all length-n closed directed walks in \(\Pi \) and the set of all number-conserving non-uniform one-dimensional binary CAs with radius 3/2 on a finite grid with n cells (assuming that \(n\ge 7\)). Thus, the directed graph \(\Pi \) facilitates the study of such CAs regardless of the length of the grid (as long as it has at least seven cells).
Advertisement
The paper is organized as follows. Section 2 presents all necessary definitions, restricting to the formalities that are needed for a proper understanding of this paper. In Sect. 3, we reduce the set of all possible local rules to some relatively small subset of local rules that can jointly form a non-uniform CA of the considered type. Section 4 contains the main idea and the construction of the directed graph \(\Pi \). In Sect. 5 we show an example of the exploration of the graph \(\Pi \). Finally, we formulate some open problems in Sect. 6.
2 Preliminaries
In this paper, we will consider one-dimensional binary CAs with radius 3/2 on finite grids. Such a radius means that each cell has a neighborhood consisting of four cells only. We start with recalling some standard definitions.
2.1 The cellular space and configurations
For a positive integer n, \({\mathcal {G}} _n\) refers to the grid of n cells denoted \(0,1,\ldots ,n-1\), i.e.,
Any n-tuple \({\textbf{x}}=(x_0,x_1,\ldots ,x_{n-1})\in X_n = \{0,1\}^n\) is called a configuration (of length n) and represents the states of the cells in \({\mathcal {G}} _n\): the state of cell \(i\in {\mathcal {G}} _n\) in a configuration \({\textbf{x}}\) is denoted by \(x_i\). For the sake of brevity, we will sometimes express configurations in a more compact form and write them without commas. Since the grid \({\mathcal {G}} _n\) is finite, we have to choose a type of boundary conditions. In this paper, we deal with the most commonly used one, the so-called periodic boundary conditions: the last cell \(n-1\) is adjacent to the first cell 0 (so, the cells are arranged along a circle), hence, all operations on indices are performed modulo n. In particular, for each configuration \({\textbf{x}}\in X_n\), we define additionally that \(x_{-1} = x_{n-1}\), \(x_n = x_0\) and \(x_{n+1} = x_1\).
By \({\textbf{0}}\) (resp. \({\textbf{1}}\)) we denote the configuration \((00\ldots 0)\) (resp. \((11\ldots 1)\)), irrespective of its length, as this should not lead to confusion. For a configuration \({\textbf{x}}\in X_n\), we denote by \(\mu ({\textbf{x}})\) the sum of all states in \({\textbf{x}}\), i.e., \(\displaystyle {\mu ({\textbf{x}}) = \sum \nolimits _{i\in {\mathcal {G}}_n}x_i}\).
2.2 Local and global rules with neighborhood size four
A one-dimensional binary local rule with neighborhood size four is any function \(f:\{0,1\}^4\rightarrow \{0,1\}\). Hence, there are as many as \(2^{2^4}=2^{16}=65\,536\) such functions, numbered from 0 up to 65535,1 where the number is given by the formula
according to the system introduced by Wolfram (1984). However, to compress the rule numbers, we will usually write them in the hexadecimal representation (in such a way the local rules are numbered from 0 up to FFFF). The set of all such local rules will be denoted by \({\mathcal {F}}\). If \(f\in {\mathcal {F}}\) satisfies \(f(0,0,0,0) = 0\), then it is called legal and it is called double-legal (or double-quiescent) if it additionally satisfies \(f(1,1,1,1) = 1\). The subset of \({\mathcal {F}}\) consisting of local rules that are double-legal will be denoted by \(\mathcal {F_D}\). It is easy to check that \(|\mathcal {F_D}|=16\,384\).
Typically, a local rule \(f\in {\mathcal {F}}\) is defined via the so-called lookup table (LUT), where all values of f are given in the form of a table (see, e.g., Table 2). There is also a convention that the value f(x, y, z, u) is referred to as \(l_{8x+4y+2z+u}\). However, for our purpose, we will often identify f with a polynomial of four variables \({\tilde{f}}\) chosen so that its values agree with the values of f in the following sense: \({\tilde{f}}|_{\{0,1\}^4} = f\). Of course, there are many such polynomials, but if we additionally demand that it be the simplest possible, i.e., linear with respect to each of the variables, we get only one. Such a polynomial is given by the following formula:
where \(x^{(1)}=x\) and \(x^{(0)}={\overline{x}}\) (here we use the generally accepted notation for binary states: \({\bar{s}}=1-s\)). One can also use the method of “fuzzification" of the disjunctive normal form of a given local rule described in El Yacoubi and Mingarelli (2011). After writing it out, it looks quite tedious:
In this way, with each local rule \(f\in {\mathcal {F}}\), we associate four polynomials, which will allow us to express certain properties of f in a simple manner.
For \(f\in {\mathcal {F}}\), its conjugation \(f^\text {C} \) and reflection \(f^\text {R} \) are defined by
Note that both transformations \(\text {C} \) and \(\text {R} \) are involutions, i.e., \((f^\text {C} )^\text {C} =f\) and \((f^\text {R} )^\text {R} =f\). In this way, for each \(f\in {\mathcal {F}}\), we have up to three local rules that are equivalent to it: \(f^\text {C} \), \(f^\text {R} \) and \(f^{\text {C} \text {R} }\) (which is equal to \(f^{\text {R} \text {C} }\), since \(\text {C} \) and \(\text {R} \) commute).
Let \(f\in {\mathcal {F}}\) be given. Having its polynomials \(L_f\), \(C_f\), \(P_f\) and \(R_f\), it is easy to determine the corresponding polynomials for \(f^\text {C} \), \(f^\text {R} \) and \(f^{\text {C} \text {R} }\). Indeed, for example, we have
In the classical (uniform) case, each local rule \(f:\{0,1\}^{4}\rightarrow \{0,1\}\), considered on a given grid \({\mathcal {G}}_n\), generates the global rule \(F_n: X_n \rightarrow X_n\) in the following way:
The effect of the transformations \(\text {C} \) and \(\text {R} \) on a given CA, and especially on the resulting space-time diagrams, is well known. However, due to the lack of symmetry in the considered neighborhood of a cell (one neighbor on the left and two neighbors on the right), the following phenomenon is observed (see Fig. 1): the reflection \(\text {R} \) does not act like a simple mirror reflection, but is a combination of mirroring and shifting left by one cell.
Each rule sequence \([f_{0},f_{1},\ldots ,f_{n-1}]\in {\mathcal {F}}^n\) induces a non-uniform CA \(H:X_n\rightarrow X_n\) defined by, for any \({\textbf{x}}\in X_n\) and \(i\in {\mathcal {G}}_n\):
Figure 2 presents a schematic view of the action of a non-uniform CA on the grid \({\mathcal {G}}_n\). For convenience, we will sometimes compress the rule strings under consideration and, for example, write \([(f)^n]\) instead of \([f,f,\ldots ,f]\).
Due to the use of periodic boundary conditions, the number of significantly different non-uniform CAs that we can obtain in this way is less than \(65\,536^n\), since, for example, \([f_{0},f_{1},\ldots ,f_{n-2},f_{n-1}]\) and \([f_{1},f_{2},\ldots ,f_{n-1},f_{0}]\) should be treated as equivalent. However, there are at least \(65\,536^n/n\) of them, which makes it practically infeasible to search the entire set to select elements with the desired property.
Fig. 2
Schematic view of the action of a non-uniform CA \(H=[f_{0},f_{1},\ldots ,f_{n-1}]\) on the grid \({\mathcal {G}}_n\). Here \({\textbf{x}}\in X_n\) and \({\textbf{y}}=H({\textbf{x}})\)
Below we define the main property of CAs that is investigated in this paper: number conservation, which simply means that a given CA preserves the number of 1 s in any configuration throughout its evolution.
Definition 1
A non-uniform CA H on \({\mathcal {G}}_n\) is called number-conserving if \(\mu (H({\textbf{x}})) = \mu ({\textbf{x}})\) for each configuration \({\textbf{x}}\in X_n\).
In the uniform case, there are only 22 local rules in \({\mathcal {F}}\) that are number-conserving (see, e.g., Boccara and Fukś 1998). We prefer to label them \(\texttt {NC}_{i}\) for \(i\in \{0, 1, \ldots , 21\}\) rather than by their hexadecimal number. Moreover, the local rule \(f=\texttt {NC}_{16}\) is the identity rule, i.e., \(f(x,y,z,u)=y\) and for any \(n\ge 1\) the corresponding global rule \(F_n\) is simply the identity function on \(X_n\), so we prefer to denote it by \(\texttt {Id}\). All these local rules are given in Table 2 by their LUTs.
Table 2
The list of number-conserving local rules belonging to \({\mathcal {F}}\)
f
Hex
lookup table of f
\(f^{\text {C} }\)
\(f^{\text {R} }\)
\(f^{\text {C} \text {R} }\)
1111
1110
1101
1100
1011
1010
1001
1000
0111
0110
0101
0100
0011
0010
0001
0000
\(\texttt {NC}_{0}\)
AAAA
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
\(\texttt {NC}_{0}\)
\(\texttt {NC}_{21}\)
\(\texttt {NC}_{21}\)
\(\texttt {NC}_{1}\)
ABA8
1
0
1
0
1
0
1
1
1
0
1
0
1
0
0
0
\(\texttt {NC}_{14}\)
\(\texttt {NC}_{20}\)
\(\texttt {NC}_{5}\)
\(\texttt {NC}_{2}\)
B8B8
1
0
1
1
1
0
0
0
1
0
1
1
1
0
0
0
\(\texttt {NC}_{12}\)
\(\texttt {NC}_{19}\)
\(\texttt {NC}_{9}\)
\(\texttt {NC}_{3}\)
BC8C
1
0
1
1
1
1
0
0
1
0
0
0
1
1
0
0
\(\texttt {NC}_{8}\)
\(\texttt {NC}_{18}\)
\(\texttt {NC}_{13}\)
\(\texttt {NC}_{4}\)
BE82
1
0
1
1
1
1
1
0
1
0
0
0
0
0
1
0
\(\texttt {NC}_{4}\)
\(\texttt {NC}_{15}\)
\(\texttt {NC}_{15}\)
\(\texttt {NC}_{5}\)
BF80
1
0
1
1
1
1
1
1
1
0
0
0
0
0
0
0
\(\texttt {NC}_{20}\)
\(\texttt {NC}_{14}\)
\(\texttt {NC}_{1}\)
\(\texttt {NC}_{6}\)
C8F8
1
1
0
0
1
0
0
0
1
1
1
1
1
0
0
0
\(\texttt {NC}_{11}\)
\(\texttt {NC}_{17}\)
\(\texttt {NC}_{10}\)
\(\texttt {NC}_{7}\)
CCCC
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
\(\texttt {NC}_{7}\)
\(\texttt {NC}_{16}\)
\(\texttt {NC}_{16}\)
\(\texttt {NC}_{8}\)
CEC2
1
1
0
0
1
1
1
0
1
1
0
0
0
0
1
0
\(\texttt {NC}_{3}\)
\(\texttt {NC}_{13}\)
\(\texttt {NC}_{18}\)
\(\texttt {NC}_{9}\)
CFC0
1
1
0
0
1
1
1
1
1
1
0
0
0
0
0
0
\(\texttt {NC}_{19}\)
\(\texttt {NC}_{12}\)
\(\texttt {NC}_{2}\)
\(\texttt {NC}_{10}\)
DCD0
1
1
0
1
1
1
0
0
1
1
0
1
0
0
0
0
\(\texttt {NC}_{17}\)
\(\texttt {NC}_{11}\)
\(\texttt {NC}_{6}\)
\(\texttt {NC}_{11}\)
E0EC
1
1
1
0
0
0
0
0
1
1
1
0
1
1
0
0
\(\texttt {NC}_{6}\)
\(\texttt {NC}_{10}\)
\(\texttt {NC}_{17}\)
\(\texttt {NC}_{12}\)
E2E2
1
1
1
0
0
0
1
0
1
1
1
0
0
0
1
0
\(\texttt {NC}_{2}\)
\(\texttt {NC}_{9}\)
\(\texttt {NC}_{19}\)
\(\texttt {NC}_{13}\)
E3E0
1
1
1
0
0
0
1
1
1
1
1
0
0
0
0
0
\(\texttt {NC}_{18}\)
\(\texttt {NC}_{8}\)
\(\texttt {NC}_{3}\)
\(\texttt {NC}_{14}\)
EA2A
1
1
1
0
1
0
1
0
0
0
1
0
1
0
1
0
\(\texttt {NC}_{1}\)
\(\texttt {NC}_{5}\)
\(\texttt {NC}_{20}\)
\(\texttt {NC}_{15}\)
EB28
1
1
1
0
1
0
1
1
0
0
1
0
1
0
0
0
\(\texttt {NC}_{15}\)
\(\texttt {NC}_{4}\)
\(\texttt {NC}_{4}\)
\(\texttt {NC}_{16}\)
F0F0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
\(\texttt {NC}_{16}\)
\(\texttt {NC}_{7}\)
\(\texttt {NC}_{7}\)
\(\texttt {NC}_{17}\)
F4C4
1
1
1
1
0
1
0
0
1
1
0
0
0
1
0
0
\(\texttt {NC}_{10}\)
\(\texttt {NC}_{6}\)
\(\texttt {NC}_{11}\)
\(\texttt {NC}_{18}\)
F838
1
1
1
1
1
0
0
0
0
0
1
1
1
0
0
0
\(\texttt {NC}_{13}\)
\(\texttt {NC}_{3}\)
\(\texttt {NC}_{8}\)
\(\texttt {NC}_{19}\)
FC0C
1
1
1
1
1
1
0
0
0
0
0
0
1
1
0
0
\(\texttt {NC}_{9}\)
\(\texttt {NC}_{2}\)
\(\texttt {NC}_{12}\)
\(\texttt {NC}_{20}\)
FE02
1
1
1
1
1
1
1
0
0
0
0
0
0
0
1
0
\(\texttt {NC}_{5}\)
\(\texttt {NC}_{1}\)
\(\texttt {NC}_{14}\)
\(\texttt {NC}_{21}\)
FF00
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
\(\texttt {NC}_{21}\)
\(\texttt {NC}_{0}\)
\(\texttt {NC}_{0}\)
Of course, in the uniform case, if a given local rule f is number-conserving, then \(f^\text {C} \), \(f^\text {R} \) and \(f^{\text {C} \text {R} }\) are also number-conserving. The same principle also holds true in the non-uniform case, i.e., if \(H=[f_{0},f_{1},\ldots ,f_{n-1}]\) is number-conserving, then so are \(H^\text {C} =[f_{0}^\text {C} ,f_{1}^\text {C} ,\ldots ,f_{n-1}^\text {C} ]\), \(H^\text {R} =[f_{n-1}^\text {R} ,f_{n-2}^\text {R} ,\ldots ,f_{0}^\text {R} ]\) and \(H^{\text {C} \text {R} }=[f_{n-1}^{\text {C} \text {R} },f_{n-2}^{\text {C} \text {R} },\ldots ,f_{0}^{\text {C} \text {R} }]\).
Fig. 3
Space-time diagrams of sample non-uniform CAs starting from the initial configuration \({\textbf{x}}=(0,0,0,1,1,1,1,0,0)\). The rule sequences are indicated above the first row. The CA in a is number-conserving, while that in b is not number-conserving
Figure 3a shows the space-time diagram of the non-uniform CA \(H=[{ \texttt {E8E8}},(\texttt {NC}_{15})^7,{ \texttt {F330}}]\), starting from a sample configuration \({\textbf{x}}=(0,0,0,1,1,1,1,0,0)\). It turns out that this CA is number-conserving, however, to confirm this, all \(2^{9}\) initial configurations had to be examined. Figure 3b shows the space-time diagram starting from the same initial configuration for the CA \(H=[{ \texttt {4211,1F27,8DF5,A2B5,C675,2E0,CC68,893C,}}{ \texttt {CDF9}}]\). As can be seen, this H is not number-conserving, which was to be expected, because the last rule, \(f_8={ \texttt {CDF9}}\), satisfies \(f_8(0,0,0,0)=1\). Indeed, the following observation holds.
Lemma 1
If \(H=[f_0,f_1,\ldots ,f_{n-1}]\) is number-conserving, then \(f_i\in \mathcal {F_D}\), for each \(i\in \{0,1,\ldots ,n-1\}\).
Proof
If H is number-conserving on \({\mathcal {G}}_n\), then it should hold that \(H({\textbf{0}}) = {\textbf{0}}\) and \(H({\textbf{1}}) = {\textbf{1}}\), so we get \(f_i(0,0,0,0) = 0\) and \(f_i(1,1,1,1)=1\), for each \(i\in \{0,1,\ldots ,n-1\}\). This proof can be found, for example, in Wolnik et al. (2023a), we quote it only for the reader’s convenience. \(\square \)
The condition given in Lemma 1 is only a necessary condition, not a sufficient one. As will be seen later, only a small subset of local rules from \(\mathcal {F_D}\) can contribute to a number-conserving rule sequence \([f_0,f_1,\ldots ,f_{n-1}]\) (as long as the grid is not too short).
3 The set of admissible local rules
In Wolnik et al. (2023a), where an exhaustive characterization of all non-uniform ECAs was established, it turned out that if a grid has at least five cells, only nine Wolfram rules can jointly form a number-conserving rule sequence (see also Hazari and Das 2016). In this section we want to obtain some similar results in the case of radius 3/2. We start by proving a necessary and sufficient condition (similarly to Wolnik et al. 2023a). It is important to emphasize that all results in this section refer to grids that have at least seven cells. (For reasons of simplicity, we often drop the commas and write, for example, f(1110) instead of f(1, 1, 1, 0).)
3.1 A necessary and sufficient condition
Theorem 1
Let \(n\ge 7\) and \(f_0,f_1,\ldots ,f_{n-1}\in {\mathcal {D}}\). Then \(H = [f_0,f_1,\ldots ,f_{n-1}]\) is number-conserving if and only if for each \(i\in \{0,1,\ldots ,n-1\}\) and for all \(x,y,z,u,w,t\in \{0,1\}\), it holds that
where x, y, z, u, w, t are the states of the cells labeled \(i-3, i-2,i-1,i+1,i+2,i+3\), respectively. If H is number-conserving, then \(\mu (H({\textbf{x}})) = \mu ({\textbf{x}})\) and \(\mu (H({\textbf{x}}')) = \mu ({\textbf{x}}')\). In particular, \(\mu (H({\textbf{x}})) - \mu (H({\textbf{x}}')) = \mu ({\textbf{x}}) - \mu ({\textbf{x}}') = 1\). Since \(H({\textbf{x}})\) and \(H({\textbf{x}}')\) may differ only at cells labeled \(i-2\), \(i-1\), i and \(i+1\), it follows that
Moreover, the above consideration shows that if \(\mu (H({\textbf{x}})) = \mu ({\textbf{x}})\) for all \({\textbf{x}}\in X\) with k 1 s, then condition (2) guarantees that also \(\mu (H({\textbf{x}})) = \mu ({\textbf{x}})\) for all \({\textbf{x}}\in X\) with \(k+1\) 1 s. As we assume that each \(f_i\) satisfies \(f_i(0000)=0\), we get \(H({\textbf{0}})={\textbf{0}}\), which means that \(\mu (H({\textbf{x}})) = \mu ({\textbf{x}})\) for the single \({\textbf{x}}\in X\) with no 1 s. Thus, induction yields that (2) is also a sufficient condition. \(\square \)
A careful study of the necessary and sufficient condition stated in Theorem 1 leads to the following corollary.
Corollary 1
If \(n\ge 7\) and \(H=[f_0,f_1,\ldots ,f_{n-1}]\) is number-conserving, then \(f_0,f_1,\ldots ,f_{n-1}\in {\mathcal {S}}\), where \({\mathcal {S}}\) is the set of all double-legal CAs satisfying:
We can choose solutions for every equation independently from each other. This means that we can obtain as many as \(3\cdot 6\cdot 6\cdot 3 = 324\) different solutions of (3).
Let us now assume that \(n\ge 7\) and \(H=[f_0,f_1,\ldots ,f_{n-1}]\) is number-conserving. Then according to Lemma 1, each \(f_i\) is double-legal. Since \(n\ge 7\), condition (2) holds. Setting \(x=1\) and \(x=0\) into Eq. (2), we obtain
From Eqs. (7)–(10) we conclude that \(f_{i-2}\in {\mathcal {S}}\). As \(i\in \{0, \ldots , n-1\}\) can be chosen freely, we have thus proven that \(f_0, f_1, \ldots , f_{n-1}\in {\mathcal {S}}\). \(\square \)
Note that Corollary 1, like Lemma 1, is only a necessary condition, but it greatly reduces the number of rules that can jointly form number-conserving non-uniform CA: from \(16\,384\) to 324. This made it possible to commence a computer-assisted exhaustive search for number-conserving non-uniform CAs.
3.2 Further reduction of the set of admissible local rules
The first computer experiments conducted on a grid of length seven showed that number-conserving CAs \([f_0, f_1, \ldots , f_{6}]\) do not contain all rules from \({\mathcal {S}}\). This gave rise to the supposition that perhaps the condition in Corollary 1 can be further improved. And indeed, it turns out that the set \({\mathcal {S}}\) can be quite easily narrowed down to a set \({\mathcal {A}}\) containing only 242 local rules. For this purpose, it suffices to use discrete derivatives.
Note that the necessary and sufficient condition formulated in Theorem 1 (Eq. (2)) is equivalent to the following identity on polynomials:
This means, among other things, that the polynomials \(L_{f_{i-2}}(x,y,z)\) and \(R_{f_{i+1}}(u,w,t)\) must be independent of x and t, respectively, since these variables do not appear in the other polynomials. Moreover, if, for example, \(L_{f_{i-2}}(x,y,z)\) contains the component ‘\(+2yz\)’, then \(C_{f_{i-1}}(y,z,u)\) must contain the component ‘\(-2yz\)’, since the variable y appears neither in \(P_{f_{i}}(z,u,w)\) nor in \(R_{f_{i+1}}(u,w,t)\).
Following this idea, let \({\mathcal {L}}=\{ L_f(x,y,z) \mid f\in {\mathcal {S}}\}\), \({\mathcal {C}}=\{ C_f(y,z,u) \mid f\in {\mathcal {S}}\}\), \({\mathcal {P}}=\{ P_f(z,u,w) \mid f\in {\mathcal {S}}\}\) and \({\mathcal {R}}=\{ R_f(u,w,t) \mid f\in {\mathcal {S}}\}\). It turns out that the cardinalities of these collections are quite small: \(|{\mathcal {L}}|=|{\mathcal {R}}|=36\) and \(|{\mathcal {C}}|=|{\mathcal {P}}|=169\), so for every \(L\in {\mathcal {L}}\) it can easily be checked whether it is admissible, i.e., there exist \(C\in {\mathcal {C}}\), \(P\in {\mathcal {P}}\) and \(R\in {\mathcal {R}}\) for which \(L+C+P+R=1\). We denote the set of all admissible \(L\in {\mathcal {L}}\) by \({\mathcal {L}}_A\). Similarly, let \({\mathcal {C}}_A\), \({\mathcal {P}}_A\) and \({\mathcal {R}}_A\) be the sets of admissible elements of \({\mathcal {C}}\), \({\mathcal {P}}\) and \({\mathcal {R}}\), respectively. It appears that \(|{\mathcal {L}}_A|=|{\mathcal {R}}_A|=25\) and \(|{\mathcal {C}}_A|=|{\mathcal {P}}_A|=131\).
If a local rule f jointly forms some number-conserving CA \([f_0, f_1, \ldots , f_{n-1}]\) on a grid consisting of at least seven cells, then, according to Eq. (11), \(L_f\in {\mathcal {L}}_A\), \(C_f\in {\mathcal {C}}_A\), \(P_f\in {\mathcal {P}}_A\) and \(R_f\in {\mathcal {R}}_A\). This allows us to narrow down the set \({\mathcal {S}}\) to the following one:
The set \({\mathcal {A}}\) contains 242 local rules only.
Our findings so far can be summarized in the following conclusion.
Corollary 2
If \(n\ge 7\) and \(H=[f_0,f_1,\ldots ,f_{n-1}]\) is number-conserving, then \(f_0,f_1,\ldots ,f_{n-1}\in {\mathcal {A}}\).
The question immediately arises whether the set \({\mathcal {A}}\) can be narrowed down even further. The answer turned out to be surprising: yes, but, as our investigations below will show, only two local rules will fall off, that is, the set of all local rules from \({\mathcal {F}}\) that can jointly form a number-conserving H on a grid consisting of at least seven cells, has exactly 240 elements. After partitioning \({\mathcal {A}}\) into equivalence classes according to the transformations \(\text {C} \) and \(\text {R} \), i.e., into classes of type \(\{f,f^\text {C} ,f^\text {R} ,f^{\text {C} \text {R} }\}\), we get exactly 66 disjoint classes, including as many as 55 four-element classes and only 11 two-element classes. Table 3 shows one representative from each class. As will become clear further on, the 58th rule C4F4 (as well as its conjugation D0DC) does not appear in any non-uniform number-conserving CA on a grid of length at least 7.
Table 3
Representatives of all 66 equivalence classes of type \(\{f,f^\text {C} ,f^\text {R} ,f^{\text {C} \text {R} }\}\), into which \({\mathcal {A}}\) is partitioned by the transformations \(\text {C} \) and \(\text {R} \). The 58th rule is shown in bold font due to its particular properties (see text)
f
LUT
f
LUT
0
\({ \texttt {8080}}\)
1000000010000000
33
\({ \texttt {A8A8}}\)
1000000010000000
1
\({ \texttt {808C}}\)
1000000010001100
34
\({ \texttt {AAAA}}\)
1000000010001100
2
\({ \texttt {80B0}}\)
1000000010110000
35
\({ \texttt {ABA8}}\)
1000000010110000
3
\({ \texttt {80BC}}\)
1000000010111100
36
\({ \texttt {ACA0}}\)
1000000010111100
4
\({ \texttt {8282}}\)
1000001010000010
37
\({ \texttt {ACAC}}\)
1000001010000010
5
\({ \texttt {828E}}\)
1000001010001110
38
\({ \texttt {AEA2}}\)
1000001010001110
6
\({ \texttt {82B2}}\)
1000001010110010
39
\({ \texttt {AFA0}}\)
1000001010110010
7
\({ \texttt {82BE}}\)
1000001010111110
40
\({ \texttt {AFAC}}\)
1000001010111110
8
\({ \texttt {8380}}\)
1000001110000000
41
\({ \texttt {B080}}\)
1000001110000000
9
\({ \texttt {8888}}\)
1000100010001000
42
\({ \texttt {B08C}}\)
1000100010001000
10
\({ \texttt {88B8}}\)
1000100010111000
43
\({ \texttt {B0B0}}\)
1000100010111000
11
\({ \texttt {8A8A}}\)
1000101010001010
44
\({ \texttt {B0BC}}\)
1000101010001010
12
\({ \texttt {8ABA}}\)
1000101010111010
45
\({ \texttt {B282}}\)
1000101010111010
13
\({ \texttt {8B88}}\)
1000101110001000
46
\({ \texttt {B2B2}}\)
1000101110001000
14
\({ \texttt {8BB8}}\)
1000101110111000
47
\({ \texttt {B888}}\)
1000101110111000
15
\({ \texttt {8C80}}\)
1000110010000000
48
\({ \texttt {B8B8}}\)
1000110010000000
16
\({ \texttt {8C8C}}\)
1000110010001100
49
\({ \texttt {BC80}}\)
1000110010001100
17
\({ \texttt {8CB0}}\)
1000110010110000
50
\({ \texttt {BC8C}}\)
1000110010110000
18
\({ \texttt {8CBC}}\)
1000110010111100
51
\({ \texttt {BCB0}}\)
1000110010111100
19
\({ \texttt {8E82}}\)
1000111010000010
52
\({ \texttt {BCBC}}\)
1000111010000010
20
\({ \texttt {8E8E}}\)
1000111010001110
53
\({ \texttt {BE82}}\)
1000111010001110
21
\({ \texttt {8EB2}}\)
1000111010110010
54
\({ \texttt {C0C0}}\)
1000111010110010
22
\({ \texttt {8F80}}\)
1000111110000000
55
\({ \texttt {C0CC}}\)
1000111110000000
23
\({ \texttt {8F8C}}\)
1000111110001100
56
\({ \texttt {C0F0}}\)
1000111110001100
24
\({ \texttt {8FB0}}\)
1000111110110000
57
\({ \texttt {C0FC}}\)
1000111110110000
25
\({ \texttt {8FBC}}\)
1000111110111100
58.
C4F4
1000111110111100
26
\({ \texttt {9090}}\)
1001000010010000
59
\({ \texttt {C8C8}}\)
1001000010010000
27
\({ \texttt {9898}}\)
1001100010011000
60
\({ \texttt {C8F8}}\)
1001100010011000
28
\({ \texttt {9C90}}\)
1001110010010000
61
\({ \texttt {CCC0}}\)
1001110010010000
29
\({ \texttt {A0A0}}\)
1010000010100000
62
\({ \texttt {CCCC}}\)
1010000010100000
30
\({ \texttt {A0AC}}\)
1010000010101100
63
\({ \texttt {CCF0}}\)
1010000010101100
31
\({ \texttt {A2A2}}\)
1010001010100010
64
\({ \texttt {E8E8}}\)
1010001010100010
32
\({ \texttt {A3A0}}\)
1010001110100000
65
\({ \texttt {ECE0}}\)
1010001110100000
4 The directed graph \(\Pi \)
In this section we describe how to generate a directed graph \(\Pi = (V, E)\) with the following property: for each \(n\ge 7\) there is a one-to-one correspondence between the set of all number-conserving non-uniform one-dimensional binary CAs with radius 3/2 on a finite grid with n cells and the set of all length-n closed directed walks in this graph (by a closed directed walk we mean a sequence of connected vertices of which the first and last are the same with repetition of edges and vertices allowed).
4.1 The idea behind the graph
Let us start with an example. Figure 3 presents a space-time diagram of the non-uniform CA \(H=[{ \texttt {E8E8}},(\texttt {NC}_{15})^7,{ \texttt {F330}}]\) on the grid \({\mathcal {G}}_9\). To find out whether H is number-conserving or not, we checked all \(2^9=512\) elements \({\textbf{x}}\in X_9\), to verify whether \(\mu \big (H({\textbf{x}})\big )=\mu ({\textbf{x}})\) holds. However, it can be approached differently, by using the necessary and sufficient condition formulated in Theorem 1. To do this, as \(H=[{\textsf{G}},{\textsf{R}},{\textsf{R}},{\textsf{R}},{\textsf{R}},{\textsf{R}},{\textsf{R}},{\textsf{R}},{\textsf{O}}]\), where \({\textsf{G}}={ \texttt {E8E8}}\), \({\textsf{R}}=\texttt {NC}_{15}\) and \({\textsf{O}}={ \texttt {F330}}\), it is sufficient to check whether the following quadruples of local rules satisfy Eq. (11):
Using Table 4, we can do this without too much trouble. Moreover, using Table 4, we can also answer the question of what all non-uniform H that are composed only of \({\textsf{G}}\), \({\textsf{R}}\) and \({\textsf{O}}\) look like. Indeed, let \(\Lambda = (V_{\Lambda }, E_{\Lambda })\) be the directed graph, where the set of vertices \(V_{\Lambda }\) consists of all quadruples of local rules \((a,b,c,d) \in \{{\textsf{G}}, {\textsf{R}}, {\textsf{O}} \}^4\) that satisfy condition (11), and the set of edges \(E_{\Lambda }\) contains only the pairs \((v_1, v_2)\in V^2\) such that \(v_1=(a,b,c,d)\) and \(v_2= (b,c,d,e)\), for some \(a,b,c,d,e \in \{{\textsf{G}}, {\textsf{R}}, {\textsf{O}} \}\). It turns out that the graph \(\Lambda \) (see Fig. 4) has 13 vertices and 21 edges.
Table 4
The polynomials L, C, P and R for the local rules \({\textsf{G}}={ \texttt {E8E8}}\), \({\textsf{R}}=\texttt {NC}_{15}\) and \({\textsf{O}}={ \texttt {F330}}\)
f
\(L_f(x,y,z)\)
\(C_f(y,z,u)\)
\(P_f(z,u,w)\)
\(R_f(u,w,t)\)
\({\textsf{G}}={ \texttt {E8E8}}\)
\(y+z-2yz\)
\(u+z-2uz\)
\(u+w-2uw\)
0
\({\textsf{R}}=\texttt {NC}_{15}\)
\(y+z-2yz\)
\(u-y-2uz+2yz\)
\(w+z-2uw+2uz\)
\(1-u-w+2uw\)
\({\textsf{O}}={ \texttt {F330}}\)
0
\(-y-z+2yz\)
\(1-u-z+2uz\)
\(1-u-w+2uw\)
Fig. 4
The directed graph \(\Lambda \), where \({\textsf{R}}=\texttt {NC}_{15}\), \({\textsf{O}}={ \texttt {F330}}\), and \({\textsf{G}}={ \texttt {E8E8}}\)
Every number-conserving \(H=[f_0,f_1,\ldots , f_{n-1}]\), where \(n\ge 7\) and all \(f_i\in \{{\textsf{G}}, {\textsf{R}}, {\textsf{O}} \}\), determines a closed directed walk in this graph passing successively through vertices \((f_0,f_1,f_2,f_3)\), \((f_1,f_2,f_3,f_4)\), ..., \((f_{n-4}, f_{n-3}, f_{n-2}, f_{n-1})\), \((f_{n-3}, f_{n-2}, f_{n-1}, f_{0})\), \((f_{n-2}, f_{n-1}, f_{0}, f_{1})\), \((f_{n-1}, f_{0}, f_{1}, f_{2})\) and back to \((f_0,f_1,f_2,f_3)\). Since every closed directed walk can be decomposed into cycles, it is sufficient to find all cycles in this graph to describe such walks. Table 5 lists all 15 cycles in \(\Lambda \).
Table 5
All cycles in the directed graph \(\Lambda \) with their length
We are not going to perform a full analysis of the directed graph \(\Lambda \), since it contains only 3 of the 242 rules that constitute \({\mathcal {A}}\). In the next subsection we describe how to construct the entire graph.
4.2 Construction and properties of the directed graph \(\Pi \)
We start with defining an initial graph \(\Pi ^{(0)}\) as the directed graph \((V^{(0)}, E^{(0)})\), where the set of vertices \(V^{(0)}\) consists of all the quadruples of local rules \((a,b,c,d) \in {\mathcal {A}}^4\) that satisfy condition (11), and the set of edges \(E^{(0)}\) contains only these ordered pairs \((v_1, v_2)\in V^2\) such that \(v_1=(a,b,c,d)\) and \(v_2= (b,c,d,e)\), for some \(a,b,c,d \in {\mathcal {A}}\). The generation of the graph \(\Pi ^{(0)} = (V^{(0)}, E^{(0)})\) is presented in Algorithm 1. The graph \(\Pi ^{(0)}\) contains as many as \(1\,482\,863\) vertices and \(6\,804\,960\) edges.
Algorithm 1
Generation of the initial graph \(\Pi ^{(0)} = (V^{(0)}, E^{(0)})\)
However, it turns out that most of the vertices of \(\Pi ^{(0)}\) do not belong to any directed cycle and, for this reason, they cannot jointly form any non-uniform H and can be removed without harm to get the final graph \(\Pi \). More precisely, we generate the graph \(\Pi ^{(i)} = (V^{(i)}, E^{(i)})\) from the graph \(\Pi ^{(i-1)}\) for \(i\ge 1\) by removing all the vertices \(v\in V^{(i-1)}\) that do not have outgoing or incoming edges. Computer calculations show that the graph stabilizes after two reduction steps, i.e., \(\Pi ^{(2)} = \Pi ^{(3)}\), resulting in the graph \(\Pi = \Pi ^{(2)}\) containing \(273\,538\) vertices (\(18\%\) of the vertices of \(\Pi ^{(0)}\)) and \(2\,301\,044\) edges (\(34\%\) of the edges of \(\Pi ^{(0)}\)).
Using standard tools from graph theory, one can obtain that the graph \(\Pi \) satisfies the following properties:
1.
The graph \(\Pi \) has four strongly connected components \(\Pi _1\), \(\Pi _2\), \(\Pi _3\) and \(\Pi _4\) with \(136\,768\), \(136\,768\), 1 and 1 vertices, respectively. (Recall that a strongly connected component is a subset of vertices within a directed graph where every vertex is reachable from every other vertex in the subset.)
2.
Component \(\Pi _3\) contains only one vertex \((\texttt {NC}_{0},\texttt {NC}_{0},\texttt {NC}_{0},\texttt {NC}_{0})\), whereas component \(\Pi _4\) contains only the vertex \((\texttt {NC}_{21},\texttt {NC}_{21},\texttt {NC}_{21},\texttt {NC}_{21})\). Both of them contain only one edge (a loop).
Let us extend the reflection operator to vertices, edges and subgraphs of \(\Pi \) as follows:
(a)
if \(v=(a,b,c,d)\in V\), then \(v^\text {R} = (d^\text {R} ,c^\text {R} ,b^\text {R} ,a^\text {R} )\);
(b)
if \((v_1,v_2)\in E\), then \((v_1,v_2)^\text {R} =(v_2^\text {R} ,v_1^\text {R} )\);
(c)
if \(G=(V_G,E_G)\) is a subgraph of \(\Pi \), then \(G^\text {R} = (V_G^\text {R} ,E_G^\text {R} )\), where \(V_G^\text {R} =\{ v^\text {R} \mid v\in V\}\) and \(E_G^\text {R} =\{(v_1,v_2)^\text {R} \mid (v_1,v_2)\in E_G\}\).
With this convention, it holds that \(\Pi _2 = \Pi _1^\text {R} \) and \(\Pi _4 = \Pi _3^\text {R} \).
5.
Let \({\mathcal {F}}_1\subset {\mathcal {A}}\) and \({\mathcal {F}}_2\subset {\mathcal {A}}\) denote the sets of all local rules occurring at the vertices of component \(\Pi _1\) and \(\Pi _2\), respectively. Then \(|{\mathcal {F}}_1|=|{\mathcal {F}}_2|=169\) and \(|{\mathcal {F}}_1\cap {\mathcal {F}}_2|=98\). Thus \(|{\mathcal {F}}_1\cup {\mathcal {F}}_2|=240\). Moreover, \(\texttt {NC}_{0}, \texttt {NC}_{21} \in {\mathcal {F}}_1\cap {\mathcal {F}}_2\), so at the vertices of the entire graph \(\Pi \), two local rules from \({\mathcal {A}}\) do not occur. These are C4F4 and its reflection D0DC.
6.
Traversing all vertices of the graph \(\Pi _1\), we see that the minimal number of incoming edges to a vertex is 1 and the maximal number is 16, while the minimal number of outgoing edges from a vertex is 1 and the maximal number is 36.
Of course, the graph \(\Pi \) is too large to be drawn in its entirety as we did for the subgraph \(\Lambda \). However, this does not prevent its study and in the next section we present a very simple example of such an exploration.
5 A sample exploration of \(\Pi \)
In this section we illustrate how to use the directed graph \(\Pi \) to answer some questions about number-conserving non-uniform CAs on finite grids (with at least seven cells).
In Wolnik et al. (2023a) it is shown that all number-conserving ECAs with radius \(r=1\) on finite grids (consisting of at least five cells) are the classical ones (i.e., shift rules or traffic rules) or can be obtained by a concatenation of blocks belonging to only four families: , , and , where and are unique fixed-length blocks of length 1 and 2, respectively. on the grid \({\mathcal {G}}_1\) consists only of the identity rule, while on the grid \({\mathcal {G}}_2\) consists of two shifts in opposite directions. (For the reader’s convenience, we first give the rule numbers that apply in Wolnik et al. (2023a) and then the numbers that follow the convention adopted in this paper.)
and are families of blocks of length \(k+2\), defined for any natural number \(k\ge 0\) ( is simply the reflection of ). Any block can be described as consisting of a head (the leftmost rule), a body (a sequence of k occurrences of a single rule) and a tail (the rightmost rule). The family of blocks has the property that each rule sequence of the type:
(12)
is a number-conserving non-uniform ECA, regardless of the number of cells that use the identity rule to update their values. Reference (Wolnik et al. 2023a) shows that of the five uniform ECAs that are number-conserving, only two of them allow to form blocks of this kind. A natural question then arises: how about the case of radius 3/2? Do there exist blocks like this, i.e., blocks that can also be described as containing a head, a body made up of a single rule and a tail? We will allow for the possibility that the head and the tail consist of more than one rule. A rule block of this kind will be called an A-block.
To be precise, we want to find out for which local rules \({\mathcal {R}}\) from \(\{\texttt {NC}_{0},\texttt {NC}_{1},\ldots ,\texttt {NC}_{21}\}\) there exist local rules \(h_0,h_1,\ldots ,h_{l-1}\) (a head) and \(t_0,t_1,\ldots ,t_{m-1}\) (a tail), such that every A-block
is number-conserving, even if we enlarge the grid by any number of cells that use the identity rule to update their values (as in (12)). Note that we consider \(k\ge 3\) instead of \(k\ge 0\) only for our convenience and to illustrate the added value of the graph \(\Pi \).
A careful analysis of component \(\Pi _1\) (containing the vertex \((\texttt {Id},\texttt {Id},\texttt {Id},\texttt {Id})\)) helped to answer this question comprehensively. Moreover, once knowing the result, it was easy to prove, as shown below.
Theorem 2
For every \({\mathcal {R}}\in \{ \texttt {NC}_{5}\), \(\texttt {NC}_{9}\), \(\texttt {NC}_{10}\), \(\texttt {NC}_{13}\), \(\texttt {NC}_{15}\), \(\texttt {NC}_{17}\), \(\texttt {NC}_{18}\), \(\texttt {NC}_{19}\), \(\texttt {NC}_{20} \}\) there exists an A-block. Moreover:
(i)
for every such \({\mathcal {R}}\), the shortest possible head of an A-block is uniquely determined and has length 1,
(ii)
for every such \({\mathcal {R}}\), the shortest possible tail of an A-block is uniquely determined and has length 2 if \({\mathcal {R}}\in \{ \texttt {NC}_{5}, \texttt {NC}_{20} \}\) or 1 otherwise.
The shortest heads and tails of A-blocks are listed in Table 6.
Note that the blocks for \(\texttt {NC}_{9}\) and \(\texttt {NC}_{19}\) are the blocks and from Wolnik et al. (2023a)
Proof
Let \({\mathcal {R}}\in \{ \texttt {NC}_{9}\), \(\texttt {NC}_{10}\), \(\texttt {NC}_{13}\), \(\texttt {NC}_{15}\), \(\texttt {NC}_{17}\), \(\texttt {NC}_{18}\), \(\texttt {NC}_{19} \}\). We will show that the following conditions are met:
(i)
There exist a unique local rule \(h_0\) such that the quadruples \((\texttt {Id}, \texttt {Id}, \texttt {Id}, h_0)\), \((\texttt {Id},\texttt {Id},h_0,{\mathcal {R}})\), \((\texttt {Id},h_0,{\mathcal {R}},{\mathcal {R}})\), \((h_0,{\mathcal {R}},{\mathcal {R}},{\mathcal {R}})\) fulfill condition (11).
(ii)
There exists a unique local rule \(t_0\) such that the quadruples \(({\mathcal {R}},{\mathcal {R}},{\mathcal {R}}, t_0)\), \(({\mathcal {R}},{\mathcal {R}},t_0,\texttt {Id})\), \(({\mathcal {R}},t_0,\texttt {Id},\texttt {Id})\), \((t_0,\texttt {Id},\texttt {Id},\texttt {Id})\) fulfill condition (11).
Now let \({\mathcal {R}} = \texttt {NC}_{10}\) (the proof for the other local rules proceeds similarly).
Table 7
The polynomials L, C, P and R for the local rules \(\texttt {NC}_{5}\), \(\texttt {NC}_{10}\) and \(\texttt {Id}\)
f
\(L_f(x,y,z)\)
\(C_f(y,z,u)\)
\(P_f(z,u,w)\)
\(R_f(u,w,t)\)
\(\texttt {NC}_{5}\)
yz
\(uz-yz\)
\(uw-uz\)
\(1-uw\)
\(\texttt {NC}_{10}\)
\(-y+yz\)
\(y+uz-yz\)
\(1-w+uw-uz\)
\( w-uw\)
\(\texttt {Id}\)
0
0
1
0
The polynomials L, C, P and R for \(\texttt {NC}_{10}\) and \(\texttt {Id}\) are given in Table 7 and according to (11), we get the following conditions for \(L_{h_0}\), \(C_{h_0}\), \(P_{h_0}\) and \(R_{h_0}\):
and it is easy to check that there is exactly one local rule in \({\mathcal {A}}\) with such polynomials, namely \(t_0 = { \texttt {FCF0}}\), which proves (ii).
For rules \(\texttt {NC}_{5}\) and \(\texttt {NC}_{20}\), one can prove that (i) is met, but (ii) is not. Indeed, let \({\mathcal {R}} = \texttt {NC}_{5}\) (the proof for \(\texttt {NC}_{20}\) is analogous). Given the polynomials for \(\texttt {NC}_{5}\) (see Table 7, just like in the previous case, we obtain:
To find a solution, we first note that there are only two local rules in \({\mathcal {A}}\) with \(R_{t_0}(u,w,t) = 1-uw\), these being \(\texttt {NC}_{5}\) itself and \({ \texttt {FFC0}}\). As a tail of length 1 does not exist, \(t_0\ne \texttt {NC}_{5}\). Therefore, we can assume that \(t_0 = { \texttt {FFC0}}\) and substitute corresponding values for \(P_{t_0}\), \(C_{t_0}\) and \(L_{t_0}\). This leads us to a single solution of the form \((t_0, t_1) = ({ \texttt {FFC0}}, { \texttt {FFF0}})\).
We can thus provide the shortest head and tail of an A-block for every local rule \({\mathcal {R}}\in \{ \texttt {NC}_{5}, \texttt {NC}_{9}, \texttt {NC}_{10}, \texttt {NC}_{13}, \texttt {NC}_{15}, \texttt {NC}_{17}, \texttt {NC}_{18}, \texttt {NC}_{19}, \texttt {NC}_{20} \}\). In particular, we have proved that such block exists. \(\square \)
The remaining number-conserving local rules from \(\{\texttt {NC}_{0}, \texttt {NC}_{1}, \ldots ,\texttt {NC}_{21}\}\) do not form an A-block, which can be easily checked either by an exploration of the graph \(\Pi \) or using the same proof method as above. However, some of them form a B-block being the reflection of an A-block. Note that B-blocks differ from A-blocks in that, due to the asymmetrical nature of the neighborhood under consideration, they must be defined as blocks of the type
and are number-conserving, even if we enlarge the grid by any number of cells that use the shift to the left (the reflection of the identity rule) as a rule to update their values. Of course, for every \({\mathcal {R}}\in \{ \texttt {NC}_{1}\), \(\texttt {NC}_{2}\), \(\texttt {NC}_{3}\), \(\texttt {NC}_{4}\), \(\texttt {NC}_{6}\), \(\texttt {NC}_{8}\), \(\texttt {NC}_{11}\), \(\texttt {NC}_{12}\), \(\texttt {NC}_{14} \}\), as these rules are the reflections of the local rules appearing in Theorem 2, there exists a B-block with a corresponding closed directed walk in the component \(\Pi _2\). The remainder, i.e., \(\texttt {NC}_{0}\) (the double shift to the left), \(\texttt {NC}_{7}\) (the shift to the left), \(\texttt {NC}_{16}=\texttt {Id}\) and \(\texttt {NC}_{21}\) (the shift to the right) neither form A-blocks nor B-blocks.
Exploring the graph \(\Pi _1\) allowed us to discover a number of blocks with a more complicated structure that any block for radius \(r=1\), for example:
1.
Blocks consisting of a head, a body made of repeating some sequence of length 2 or more, and a tail, like these:
where the local rule \({ \texttt {FFC0}}\) is a connector of length 1.
Already this small sample exploration of the graph \(\Pi \) shows that the description of all number-conserving non-uniform one-dimensional binary CAs with radius 3/2 is not likely to be as simple as in the case of radius 1. On the other hand, the availability of the graph \(\Pi \) fuels the hope that such a description is possible eventually.
6 Conclusion and open questions
In this paper we have presented the construction of a directed graph \(\Pi \) related to the family of number-conserving non-uniform one-dimensional binary CAs with radius 3/2. We strongly believe that this graph will prove to be an instrumental tool to provide a complete and detailed description of all such CAs on finite grids in the case of periodic boundary conditions. Indeed, finding all CAs of interest on a grid of length n (for \(n\ge 7\)) simply amounts to finding all closed directed walks of length n in the graph \(\Pi \). If it is successful, we will get closer to answering the following question:
Question 1
How does the enlargement of the radius affect number-conserving non-uniform one-dimensional binary CAs?
The first, selective, exploration of the graph \(\Pi \) suggests that the answer to this question may be very difficult to obtain. The case of radius 1 turned out to be unexpectedly uncomplicated, while the results contained in Sect. 5 rather indicate that in the case of radius 3/2 the situation is much more complex.
It will certainly be much easier to find ways in which the graph should be explored to address an inquiry like this:
Question 2
Which number-conserving non-uniform one-dimensional binary CAs with radius 3/2 on finite grids with periodic boundary conditions are reversible?
Indeed, intuition tells us that it is possible to find (a) sufficient condition(s) on the vertices (edges) in \(\Pi \) “ensuring” the non-reversibility of any CAs that are encoded by the closed directed walks containing the vertex (the arc).
The last question comes up naturally. As shown in Wolnik et al. (2023a), in the case of \(r=1\) there is a close relationship between number-conserving non-uniform one-dimensional binary CAs on finite grids with periodic and with null boundary conditions.
Question 3
What do all number-conserving non-uniform one-dimensional binary CAs with radius 3/2 on finite grids with null boundary conditions look like? Which of them are reversible?
The graph constructed in this paper will certainly help to answer at least partially the above questions, and this will be an important step in understanding number-conserving non-uniform CAs.
Declarations
Conflict of interest
The authors have no relevant financial or non-financial interests to disclose.
Ethical approval
Not applicable.
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
A directed graph allowing for the exploration of the set of number-conserving non-uniform one-dimensional binary cellular automata with radius one and half
Authors
Barbara Wolnik Maciej Dziemiańczuk Bartosz Makuracki Bernard De Baets
,
,
and
, where
and
are unique fixed-length blocks of length 1 and 2, respectively.
on the grid \({\mathcal {G}}_1\) consists only of the identity rule, while
on the grid \({\mathcal {G}}_2\) consists of two shifts in opposite directions. (For the reader’s convenience, we first give the rule numbers that apply in Wolnik et al. (2023a) and then the numbers that follow the convention adopted in this paper.)
and
are families of blocks of length \(k+2\), defined for any natural number \(k\ge 0\) (
is simply the reflection of
). Any block
can be described as consisting of a head (the leftmost rule), a body (a sequence of k occurrences of a single rule) and a tail (the rightmost rule). The family of blocks
has the property that each rule sequence of the type:
and
from Wolnik et al. (2023a)