1 Introduction↩︎

Probing the ability of automata networks, specially cellular automata, to solve decision problems has received a continuous attention in the literature. Given the intrinsic local processing nature of the automata in the network, in order to facilitate the process of reaching the answer of the problem the decision process has taken the form of all automata reaching a distributed consensus, that is, their all taking on a same state, out of two, that would mean one solution or the other.

In the case of binary automata networks, the most usual situation, regardless of the kind of update employed, the networks should display only two possible attractors, the fixed points \(0^L\) and \(1^L\), for all cyclic configurations of size \(L\).

The efforts in the literature related to automata networks for solving decision problems along this line has focused on two possibilities, according to the kind of decision the network would have to make with respect to the initial configuration: the characterisation of the problem in terms of a formal language the network would be recognising or not [1], [2], or in classical benchmark problems, like the determination in the initial configuration of the parity of 1s [3], [4] or the prevailing state in number of occurrences [5], [6].

With respect to decision problems characterised as formal language recognition, [1] provides complete results in terms of regular languages recognised by one-dimensional, binary cellular automata, with radii 0.5, 1 and 1.5 over cyclic configurations and synchronous update. That reference also addressed the radius 2 case. In fact, it is reported therein that out of the entire radius 2 space (composed of \(2^{2^5}\) = 4,294,967,296 rules) computational and analytical pruning processes led to 40,941 candidate rules as possible decision problem solvers, out of which 1,121 have been completely characterised in terms of a same language recognition problem they were related with (namely, the presence of at least one 0 in the initial configuration). However, not enough detail was provided in that reference that would allow for a precise replication of the latter two rule quantities, and a revision we performed on the data employed therein did not lead to any further clarification.

In face of this, the results in [1] required a reevaluation and this is exactly what the present paper is all about. In order to go about it we started from scratch, with all \(2^{2^5}\) rules of the space, only trimmed by taking the representative of the classes of dynamical equivalence – due to negation, reflection, or the composition of both – chosen as the one with the smallest Wolfram number in the class. Then we filtered the previous set towards identifying likelier consensus type rules, by computational checking the basins of attraction of all the rules for all configuration sizes \(L\) from \(L=5\) up to \(L=20\) (stricter than in [1], where it went only up to \(L=16\)); this left 54,928 candidate rules. Out of the latter, 45,699 of them were identified as candidates for 3 well-defined decision problems, leaving the remaining 9,229 as candidates for other decision problems. Finally, out of the 45,699 candidates in the 3 classes, we provided precise formal explanation about the dynamics of 40,254 of them. So, as will become clear herein, our reevaluation of radius 2 space significantly extended what was known about the space of possible decision problems in the space, by settling the matter on many more rules and at the same time identifying a number of other candidate decision problems.

The rest of the paper is structured as follows. The next section gives all formal definitions required for what will come later. Section 3 provides an overview of the results obtained, by identifying 45,699 candidate rules in 3 decision problems. Section 4 is the core of the paper, where in the 3 classes identified, 40,254 of them were proven to truly be of the distributed consensus type. The last section wraps up the results and discusses the perspectives for handling the remaining 14,674 candidate rules and their potential as solvers of more sophisticated problems. An appendix concludes the text with a complete listing of all distributed consensus decision problems derived from the work, both those characterised here and the candidates ones.

2 Basic definitions↩︎

2.1 Cellular automata↩︎

Given a radius-\(r\) CA with local rule \(f\), such a local rule induces a global transition function (or global rule) \(F:\mathscr{C}\rightarrow \mathscr{C}\) in the set of all configurations, as follows:

\[\left(F(c)\right)_i=f(c_{i-\ceil{r}},\cdots,c_i,\cdots,c_{i+\floor{r}})\]

In order to ease the notation, \([i,j]\), with \(i<j\in\mathbb{Z}\) will denote the set of integers from \(i\) to \(j\). Then we can write \(\left(F(c)\right)_i=f(c_{[i-\ceil{r},i+\floor{r}]})\).

The orbit of \(c\) under \(f\) is the sequence \(\left(c,F(c),F^2(c),F^3(c),\cdots\right)\), in which \(F^n,n\geq 1\), denotes the iteration of \(F\) \(n\) times over \(c\).

A configuration of length \(L\) (or a length \(L\) configuration), \(L\in\mathbb{Z},L\geq 1\), is a configuration such that \(c_i=c_{i+L}\) for all \(i\in\mathbb{Z}\). Such configurations can be regarded as vectors \(c=(c_0,\cdots,c_{L-1})\in\{0,1\}^L\) and the set of all such vectors is denoted by \(\mathscr{C}_L\).

The local function \(f\) induces a global function \(F_L:\mathscr{C}_L\rightarrow\mathscr{C}_L\) in the set of all configurations of length \(L\) as follows:

\[\left(F_L(c)\right)_i=f(c_{(i-\ceil{r}) mod L},\cdots,c_i,\cdots,c_{(i+\floor{r}) mod L})\]

From now on, we will only address configurations of length \(L\), therefore, for the sake of simplicity, \(F_L\) will be denoted simply by \(F\) and the indices of the cells are always assumed to be taken modulo \(L\).

A block of length \(l\geq 1\) is a vector \(b=(b_1,\cdots,b_{l})\in\{0,1\}^l\). Such block can also be denoted by \(b=b_1\cdots b_{l}\).

Given two blocks \(b=b_1\cdots b_l\) and \(\hat{b}=\hat{b}_1\cdots\hat{b}_{\hat{l}}\), with \(l\leq \hat{l}\), we say that \(b\) is a sub-block of \(\hat{b}\) if there is \(1\leq j\leq \hat{l}\) such that \(b=\hat{b}_{[j,j+l-1]}\).

Given a configuration \(c\) of length \(L\geq 1\), we say that a block \(b=b_1\cdots b_l\) of length \(l\leq L\) is a sub-block of \(c\) if there is \(0\leq j\leq L-1\) such that \(b=c_{[j,j+l-1]}\).

Given a block \(b=b_1\cdots b_l\), \(b^n\) will denote the concatenation of block \(b\) \(n\) times, that is

\[b^n=\underbrace{b_1\cdots b_l}_{1}\underbrace{b_1\cdots b_l}_{2}\cdots\underbrace{b_1\cdots b_l}_{n}\]

The function \(\hat{f_l}\) is the extension of \(f\) to blocks of length \(l\). When \(l\) is clear from the context, we will drop it from the notation and write simply \(\hat{f}\).

2.2 Attractors↩︎

For example, a solution to the parity consensus would have

• \(\mathscr{B}_0^L=\{ c \in \mathscr{C}_L : c \text{ has an even number of cells in state } 1 \}\) and

• \(\mathscr{B}_1^L=\{ c \in \mathscr{C}_L : c \text{ has an odd number of cells in state } 1 \}\),

and a solution to the majority consensus would have \(\mathscr{B}_x^L=\{ c \in \mathscr{C}_L : c \text{ has a majority of cells in state } x \}\) for \(x\in\{0,1\}\).

In the next section we discuss how the rules studied in this paper were obtained and how they are classified in terms of the decision problem they solve for the synchronous update.

3 Radius-2 consensus rules↩︎

As explained in Section 1, here we revisited the data and analysis available in the literature for binary, radius-\(2\), one-dimensional cellular automata, with synchronous updates, over cyclic configurations.

As such, recall that we started from scratch, with all \(2^{2^5}\) rules of the space, partitioned the set into its classes of dynamical equivalence (due to the symmetries derived from negation, reflection, or the composition of both) and considered the representative rule of each class as the one with the smallest Wolfram number. Then we filtered the resulting rule set towards identifying likelier consensus type rules, by computational checking the basins of attraction of all the rules for all configuration sizes \(L\) from \(L=5\) up to \(L=20\), so that they would only feature as attractors the fixed points \(0^L\) and \(1^L\). This led to 54,928 candidate rules.

Out of the latter, 45,699 of them were identified as candidates for 3 well-defined decision problems, as listed right below, organised into 3 main rule classes (A, B and C), comprising 83.2% of the original set of candidate rules.

It should be noticed that the remaining set of 9,229 uncharacterised rules comprise three possibilities: rules that may still come to be associated to the decision problems of the 3 classes, but were left out because the characterisation we provided (to be presented in the next section) may have been incomplete; rules associated to additional decision problems, yet to be characterised (see the extensive discussion and examples in Subsection 5.2 and in the Appendix); or rules that may not be candidate decision problems at all, but were not filtered out since they were subjected only to configuration sizes up to \(L=20\).

Finally, out of the 45,699 candidates in the 3 classes, we provided precise formal explanation about the dynamics of 40,254 of them, or 88.1%, meaning that the remaining set of 5,445 rules should be added to the previous 9,229 candidate rules, thus totalling 14,674 rules, or 26.7% of all rules obtained out of the filtering process.

Summing up, out of the 54,928 radius-\(2\) consensus rules obtained for \(5 \leq L \leq 20\), at least 40,254 rules (representing, approximately, \(73.3 \%\) of the total amount of potential consensus rules) really do solve decision problems for configurations of any length \(L \geq 5\). So, as detailed below, our results on the radius 2 space significantly extended what was known about the space of possible decision problems in the space, by settling the matter on many more rules and at the same time identifying a number of other candidate decision problems.

• Class A (30,230 rules): \(\mathscr{B}^L_{(f,1)}=\{1^L\}\)

• Class B (14,680 rules): \(\mathscr{B}^L_{(f,1)} = \begin{cases} \{1^L\}, if L is odd;\\ \{1^L,(01)^{L/2},(10)^{L/2}\}, if L is even \end{cases}\)

• Class C (789 rules): \(\mathscr{B}^L_{(f,1)} = \begin{cases} \{1^L\}, if L is odd;\\ \{1^L,(01)^{L/2},(10)^{L/2}\}, if L\equiv 2 mod 4;\\ \{1^L,(01)^{L/2},(10)^{L/2},(1100)^{L/4},(1001)^{L/4},(0011)^{L/4},(0110)^{L/4}\},\\ if L\equiv 0 mod 4; \end{cases}\)

Notice that, although the rules in each class have the same attractors (at least up to \(L=20\)), the actual dynamics of the rules are not the same, i.e., their basins of attraction are different.

In the next section we show that most rules in Classes A, B and C are indeed consensus rules which have exactly the basins of attraction described above for all \(L\geq 5\).

4 Proofs↩︎

Each subsection below addresses one of the rule classes and is divided in two parts: first, we provide the proofs regarding the basins of attraction for rules in each class; then, we describe how the properties of the rules in each class were checked.

4.1 Class A↩︎

4.1.1 Proofs for Class A↩︎

Let \(f\) be a local rule in Class A. Then either \(f\) is a 0-forcing rule or there is an integer \(m\) such that \(f^m\) is a 0-forcing rule. The results below show that in either case, there are only two attractors, namely \(0^L\) and \(1^L\), and that \(\mathscr{B}_1=\{1^L\}\) and \(\mathscr{B}_0=\mathscr{C}_L-\{1^L\}\).

In other words, the results below show that rules in Class A simply detect whether or not there is at least one cell in state 0 in a configuration of length \(L\).

Let \(L\geq 2r+1\).

First, notice that \(F(0^L)=f(0^{2r+1})^L=\left[0\cdot 0\cdot \phi(0^{2r+1})\right]^L=0^L\) and \(F(1^L)=f(1^{2r+1})^L=\left[1\cdot 1\cdot \phi(1^{2r+1})\right]^L=1^L\). That is, \(0^L\) and \(1^L\) are fixed-points of length \(L\) of \(F\). In particular, \(\{1^L\}\subseteq \mathscr{B}^L_1\).

The case \(i=0\) is already proven in Proposition [prop:x0x1].

Let \(g\) be a radius-\((r+i)\) CA local rule given by \(g(x_{[-\ceil{r}-|i|,\floor{r}+|i|]})=f(x_{[-\ceil{r}-|i|,\floor{r}-|i|]})\).

Define \(\tilde{\phi}:\{0,1\}^{2(r+|i|)+1}\longrightarrow \{0,1\}\) by \(\tilde{\phi}(x_{[-\ceil{r}-|i|,\floor{r}+|i|]})=\phi(x_{[-\ceil{r}-i,\floor{r}-i]})\). That is, \(g\) is the \((-i)\)-shift of \(f\) and \(G=\sigma_{-i}\circ F\).

Notice that: \[g(x_{[-\ceil{r}-|i|,\floor{r}+|i|]})=f(x_{[-\ceil{r}-i,\floor{r}-i]})= x_0\cdot x_1\cdot \phi(x_{[-\ceil{r}-i,\floor{r}-i]})= x_0\cdot x_1\cdot\tilde{\phi}(x_{-\ceil{r}-|i|,\floor{r}+|i|}).\]

Also, since \(\tilde{\phi}(1^{2(r+|i|)+1})=\phi(1^{2r+1})=1\), \(g\) satisfies the conditions in Proposition [prop:x0x1], therefore \(0^L\) and \(1^L\) are the only attractors of length \(L\) of \(G\).

Suppose \(F\) has a fixed-point \(x\) of length \(L\) such that \(x\notin\{0^L,1^L\}\). Then we would have: \[G^L(x)=\left(\sigma_{(-i)}\circ F\right)^L(x) = \left(\sigma_{(-i)}\right)^L\left( F^L(x)\right)=\left(\sigma_{-L\cdot i}\right)(x)=\sigma_0(x)=x.\]

That is, \(x\) would belong to a limit-cycle of period \(L\) of \(G\), contradicting the fact that \(0^L\) and \(1^L\) are the only attractors of \(G\).

On the other hand, if \(F\) has a configuration \(x\) of length \(L\), \(x\notin \{0^L,1^L\}\), belonging to a limit-cycle of period \(p>1\), then we would have \(F^p(x)=x\) and: \[G^{L\cdot p}(x)=\left(\sigma_{(-i)}\circ F\right)^{L\cdot p}(x) = \left(\sigma_{(-i)}\right)^{L\cdot p}\left( F^{L\cdot p}(x)\right)=\left(\sigma_{-L\cdot p\cdot i}\right)(x)=\sigma_0(x)=x.\]

In that case, \(x\) would belong to a limit-cycle of period \(L\cdot p\) of \(G\), contradicting the fact that \(0^L\) and \(1^L\) are the only attractors of \(G\).

Therefore, the only attractors of length \(L\) of \(F\) are \(0^L\) and \(1^L\).

Moreover, assume \(c\in\mathscr{C}_L\) is such that \(c_j=0\) for some \(0\leq j\leq L-1\) and suppose \(F^k(c)=1^L\) for some integer \(k>0\). Then we would have: \[G^k(c)=(\sigma_{(-i)})^k\left((F^k)(c)\right)=\sigma_{(-k\cdot i)}(1^L)=1^L.\]

In other words, \(c\) would belong to the basin of attraction of \(1^L\) for \(G\), which is a contradiction, since \(g\) satisfies the conditions in Proposition [prop:x0x1]. Therefore, \(c\) is in the basin of attraction of \(0^L\) for \(F\).

In summary, the decision problem solved by rules described in the statement of Corollary [corol:x0x2] is simply whether or not a configuration has at least one cell in state 0.

4.1.2 Checking the properties for rules in Class A↩︎

First, for every rule \(f\) in class A we tested if there was a positive integer \(m\) such that:

• \(f^m\) is 0-forcing in positions \(0\) and \(i\), for some \(i\in\{-2,-1,1,2\}\); and/or

• \(f^m\) is 0-forcing in positions \(j\) and \(j\pm 1\) or \(j\) and \(j\pm 2\), with \(-\ceil{r}\leq j\leq \floor{r}\)

Out of the 30,230 rules in class A, 27,251 rules satisfied at least one of the conditions above was satisfied for some \(1\leq m \leq 5\). Greater values of \(m\) were not tested due to the computational cost of computing \(f^m\) (a radius-\((2m)\) rule).

Then for each \(f^m\) we computed \(\phi_{f^m}:\{0,1\}^{2mr+1}\rightarrow\{0,1\}^{2mr+1}\) such that

\[f^m(x_{[-\ceil{mr},\floor{mr}]})=x_{i_1}\cdot x_{i_2}\cdot\phi_{f^m}(x_{[-\ceil{mr},\floor{mr}]})\]

with \(i_1\) and \(i_2\) being the positions in which \(f^m\) is 0-forcing.

Finally, we checked whether or not the following conditions were satisfied:

• \(\phi_{f^m}(1^{2mr+1})=1\), for every rule in class A;

• \(\phi_{f^m}(u_{mr})=0\), with \(u_{mr}\) defined as in Corollary [corol:x0x2], for rules in class A with \((i_1,i_2)=(0,2)\) or \((i_1,i_2)=(0,-2)\).

Notice that the 27,251 rules satisfying the conditions above also satisfy the conditions in Corollary [corol:x0xicomposition], hence such rules are consensus rules with \(\mathscr{B}_1=\{1^L\}\).

Table 1 shows how many rules in Class A are such that \(f^m\) is 0-forcing, for \(1\leq m\leq 5\), in two adjacent (\(i\) and \(i\pm 1\)) or two alternated (\(i\) and \(i\pm 2\)) positions. Out of the 30,230 rules, 27,251 rules satisfy such a property for some \(1\leq m \leq 5\). Greater values of \(m\) were not tested due to computational limitations.

4.2 Class B↩︎

4.2.1 Proofs for Class B↩︎

The 14,680 rules in Class B behave as follows, for configurations of length \(5\leq L\leq 20\):

• If \(L\) is odd, \(\mathscr{B}_1^L=\{1^L\}\) and \(\mathscr{B}_0^L=\mathscr{C}_L-\{1^L\}\), that is, in such a case, the basins of attraction are exactly as the ones for the rules in Class A;

• If \(L\) is even, \(\mathscr{B}_1^L=\{1^L,(10)^{L/2},(01)^{L/2}\}\) and \(\mathscr{B}_0^L=\mathscr{C}_L-\{1^L,(10)^{L/2},(01)^{L/2}\}\).

In summary, rules in Class B detect whether or not a configuration of length \(5\leq L\leq 20\) satisfies one of the following conditions: (a) all of its cells in state 1 or; (b) every pair of adjacent cells are in distinct states (that is, if it is a 01 or 10 necklace). This will be proven below, based upon some properties of such rules.

Let \(f\) be a rule in Class B and suppose \(f\) has the following properties, for some integer \(n_1\geq 1\) and some integer \(n_2\geq 1\):

• B1) For any \(c\in\mathscr{C}_L\), such that \(c\notin\{1^L\}\), if \(L\) is odd, and \(c\notin \{1^L,(01)^{L/2},(10)^{L/2}\}\), if \(L\) is even, there is \(0\leq j\leq L-1\) such that \(\left(F^{n_1}(c)\right)_{[j,j+1]}=00\), that is, after iterating \(F\) \(n_1\) times over any configuration \(c\notin \{1^L\}\), if \(L\) is odd, and \(c\notin\{1^L,(01)^{L/2},(10)^{L/2}\}\), if \(L\) is even, the resulting configuration has two adjacent zeroes;

• B2) There is \(0\leq i\leq L-1\) such that if \(c\in\mathscr{C}_L\) is such that \(c_{[j,j+1]}=00\) for some \(0\leq j\leq L-1\), then \(\sigma_i\left(F^{n_2}(c)\right)_{[j,j+2]}=000\). In other words, every pair of adjacent zeroes in \(c\) generates a triple of adjacent zeroes in \(F^{n_2}(c)\), eventually displaced by \(i\) cells from the original position of the pair of 0s in \(c\).

• B3) \(f(0,1,0,1,0)=f(1,0,1,0,1)=f(1,1,1,1,1)=1\).

• B4) \(f(0,0,0,0,0)=0\)

We will show that rules satisfying properties B1)–B4) have exactly the basins of attraction described in the beginning of this subsection.

4.2.2 Checking the properties for rules in Class B↩︎

Each one of the \(14,680\) rules in class B satisfied properties \(B1), B3)\) and \(B4)\) and \(12,294\) of such rules also satisfied property \(B2)\) for some integer \(1\leq n_2 \leq 5\). Greater values of \(n_2\) were not tested due to computational limitations.

Such computational verifications were carried out as follows:

• Property B1): First, for all \(f\) in class B, we checked if there was an integer \(m_1>0\) for which \(f^{m_1}\) eventually preserves the existence of adjacent 0s in a configuration, that is, if \(c\in\mathscr{C}_L\) contains \(00\), then \(F^{m_1}(c)\) also contains \(00\).

  Let \(X_{(l,i)}=\{b=(b_1,\cdots,b_l)\in\{0,1\}^l:b_ib_{i+1}=00\}\) for integers \(l,i\) with \(1\leq i\leq l-1\) and \(l\geq 2\). That is, \(X_{(l,i)}\) is the set of all binary blocks of length \(l\) containing \(00\) as a sub-block in position \(i\).

  We then checked whether or not there were integers \(m_1\) and \(i_1\) such that the following condition was satisfied for every block \(x=(x_1,\cdots,x_{4m_1+2})\in X_{(4m_1+2,i_1)}\): \[\left(f^{m_1}(x_1,\cdots,x_{4m_1+1}),f^{m_1}(x_2,\cdots,x_{4m_1+2})\right)=(0,0)\]

  This shows that, if a configuration already has two adjacent 0s, then every configuration in its orbit under \(f^{m_1}\) will also have two adjacent 0s, therefore it remained to take into account configurations not containing two adjacent 0s.

  Suppose \(c\) is a configuration of length \(L\) such that \(c\) does not have adjacent cells in state 0 and \(c\notin\{1^L\}\), if \(L\) is odd, and \(c\notin\{1^L,(01)^{L/2},(10)^{L/2}\}\) if \(L\) is even. Notice that, in such a case, \(c\) must contain \(1101\) and \(1011\) as sub-blocks.

  Let \(Y_{(l,i)}=\{b=(b_1,\cdots,b_l)\in\{0,1\}^l:b_{[i,i+3]}\in\{1101,1011\}\}\) for integers \(l,i\) with \(1\leq i\leq l-3\) and \(l\geq 4\). That is, \(Y_{(l,i)}\) is the set of all binary blocks of length \(l\) containing \(1101\) or \(1011\) as a sub-block in position \(i\).

  Then, for all \(f\) in class B, we checked whether or not there were integers \(m_2>0\) and \(i_2\) such that, for every block \(y=(y_1,\cdots,y_{4m_2+2})\in Y_{(4m_2+2,i_2)}\), the following condition was satisfied: \[\left(f^{m_2}(y_1,\cdots,y_{4m_2+1}),f^{m_2}(y_2,\cdots,y_{4m_2+2})\right)=(0,0)\]

  This shows that, if a configuration \(c\) contains \(1101\) or \(1011\) as a sub-block, then \(F^{m_2}(c)\) contains two adjacent 0s.

  By taking \(n_1=max\{m_1,m_2\}\), we have that \(F^{n_1}\) satisfies the conditions in property B1).

  Table 2 shows the number of rules in class B satisfying such a condition for different values of \(n_1\). Every rule in Class B satisfied condition B1) for some integer \(n_1\).

  Table 2: Number of rules in Class B such that \(n_1\) is the smallest integer for which \(f^{n_1}\) satisfies the condition B1).

  \(n_1\)	1	2	3	4	Total
  # of rules	11,848	2,793	0	39	14,680

• Property B2): In order to verify property B2), for every \(f\) in class B we checked whether or not there were integers \(n_2\) and \(i_3\) such that, for every block \(z=(z_1,\cdots,z_{4n_2+3})\in X_{(4n_2+3,i_3)}\) ,the following condition was satisfied:

  \[\left(f^{n_2}(z_1,\cdots,z_{4n_2+1}),f^{n_2}(z_2,\cdots,z_{4n_2+2}),f^{n_2}(z_3,\cdots,z_{4n_2+3})\right)=(0,0,0)\]

  This is an extension of the preservation of adjacent 0s, and shows that, for every pair of adjacent cells in state 0 in a configuration, there is a triple of adjacent cells in state 0 in its image, possibly displaced by \(i_3\) positions to the left or to the right (depending on \(i_3\) being positive or negative) from the position of \(00\) in the original configuration.

  Table 3 shows the number of rules in class B satisfying such a condition for different values of \(n_2\). Every rule in Class B satisfied such a condition for some integer \(n_2\).

  Table 3: Number of rules in Class B such that \(n_2\) is the smallest integer for which \(f^{n_2}\) satisfies the condition B2).

  \(n_2\)	1	2	3	4	5	Total
  # of rules	1,790	4,798	1,965	2,225	1,516	12,294

• Properties B3) and B4): For every \(f\) in class B, properties B3) and B4) were readily verified by checking the images of \((0,1,0,1,0),(1,0,1,0,1),(0,0,0,0,0)\) and \((1,1,1,1,1)\) under \(f\).

Therefore, the above results show that (at least) 12,294 out of 14,680 rules in class B solve for all \(L\geq 5\) the very same decision problem solved for \(5 \leq L \leq 20\).

4.3 Class C↩︎

4.3.1 Proofs for Class C↩︎

The proofs for rules in this class are very similar to the ones for class B, as they will rely on the expansion of blocks of three consecutive 0s rather than of blocks of two consecutive 0s.

The \(789\) rules in Class C behave as follows, for configurations of length \(5 \leq L\leq 20\):

• If \(L\) is odd, \(\mathscr{B}_1^L=\{1^L\}\) and \(\mathscr{B}_0^L=\mathscr{C}_L-\{1^L\}\), that is, in such a case, the basins of attraction are exactly as the ones for the rules in Class A;

• If \(L=4p+2\) for some integer \(p\geq 1\), \(\mathscr{B}_1^L=\{1^L,(10)^{L/2},(01)^{L/2}\}\) and \(\mathscr{B}_0^L=\mathscr{C}_L-\{1^L,(10)^{L/2},(01)^{L/2}\}\). That is, in such a case, the attractors are exactly as the ones for even \(L\) for rules in Class B;

• If \(L=4p\) for some integer \(p\geq 2\), \(\mathscr{B}_1^L=\{1^L,(10)^{L/2},(01)^{L/2},(1100)^{L/4},(1001)^{L/4},(0011)^{L/4},(0110)^{L/4}\}\) and \(\mathscr{B}_0^L=\mathscr{C}_L-\{1^L,(10)^{L/2},(01)^{L/2},(1100)^{L/4},(1001)^{L/4},(0011)^{L/4},(0110)^{L/4}\}\).

In summary, rules in Class C detect whether or not a configuration of length \(L\) satisfies one of the following conditions: (a) all of its cells in state 1 or; (b) every pair of adjacent cells are in distinct states (that is, if it is a 01 or 10 necklace) or; (c) the configuration is a 1100 or 1001 or 0011 or 0110 necklace. This will be proven below, based upon some properties of such rules.

Let \(f\) be a rule in Class C and assume \(f\) has the following properties, for some integer \(n_1\geq 1\) and some integer \(n_2\geq 1\):

• C1) For any \(c\in\mathscr{C}_L\), such that \(c\notin\{1^L\}\), if \(L\) is odd, \(c\notin \{1^L,(01)^{L/2},(10)^{L/2}\}\), if \(L=4p+2\) for some \(p\geq 1\), and \(c\notin \{1^L,(10)^{L/2},(01)^{L/2},(1100)^{L/4},(1001)^{L/4},(0011)^{L/4},(0110)^{L/4}\}\), if \(L=4p\) for some \(p\geq 2\), there is \(0\leq j\leq L-1\) such that \(\left(F^{n_1}(c)\right)_{[j,j+2]}=000\), that is, after iterating \(F\) \(n_1\) times over any configuration \(c\) (as described above), the resulting configuration has three adjacent zeroes;

• C2) There is \(0\leq i\leq L-1\) such that if \(c\in\mathscr{C}_L\) is such that \(c_{[j,j+2]}=000\) for some \(0\leq j\leq L-1\), then \(\sigma_i\left(F^{n_2}(c)\right)_{[j,j+3]}=0000\). In other words, every triple of adjacent 0s in \(c\) generates a quadruple of adjacent 0s in \(F^{n_2}(c)\), eventually displaced by \(i\) cells from the original position of the triple of 0s in \(c\).

• C3) \(f(0,1,0,1,0)=f(1,0,1,0,1)=f(1,1,1,1,1)=f(1,1,0,0,1)=f(0,0,1,1,0)=1\).

• C4) \(f(0,0,0,0,0)=f(0,1,1,0,0)=f(1,0,0,1,1)=0\).

We will show that rules satisfying properties C1)–C4) have exactly the basins of attraction described in the beginning of this subsection.

4.3.2 Checking the properties for rules in Class C↩︎

Each one of the \(789\) rules in class C satisfied properties \(C3)\) and \(C4)\), \(783\) satisfied property \(C1)\) for some \(1\leq n_1 \leq 9\) and \(714\) satisfied property \(C2)\) for some integer \(1\leq n_2 \leq 5\). Greater values of \(n_1\) and \(n_2\) were not tested due to computational limitations.

Such computational verifications were carried out as follows:

• Property C1): Let \(n\) be a positive integer. A block \(b=(b_1,\cdots,b_{4n+3})\) is said to be a failing block of order \(n\) when: \[f^n(b_{[1,4n+1]})f^n(b_{[2,4n+2]})f^n(b_{[4n+3]})\neq 000\]

  In other words, a block of length \(4n+3\) is a failing block of order \(n\) when its image under \(f^n\) is not a triple of 0s.

  Let \(\mathscr{F}_n=\{b\in\{0,1\}^{4n+3}:b is a failing block of order n\}\) be the set of failing blocks of order \(n\).

  Now, consider the directed graph \(\mathcal{G}_n\) whose set of vertices is \(\mathscr{F}_n\) and the set of edges is given by: \[\mathcal{E}_n=\{(p_{[1,4n+3]},q_{[1,4n+3]})\in\mathscr{F}_n\times\mathscr{F}_n:p_{[2,4n+3]}=q_{[1,4n+2]}\}\]

  That is, the vertices in \(\mathcal{G}_n\) are the failing blocks of order \(n\) and two such blocks are connected when the last \((4n+2)\) bits of the first failing block coincide with the first \((4n+2)\) bits of the last failing block.

  Notice that cycles in \(\mathscr{G}_n\) represent (periodic) configurations consisting exclusively of failing blocks of order \(n\). That is, such configurations, when updated under \(f^n\), do not contain three adjacent 0s.

  On the other hand, any configuration that cannot be described by a cycle in such a graph must present three adjacent 0s in its image under \(f^n\), since it must contain at least one block not in \(\mathscr{F}_n\).

  For any \(n\geq 1\), \(\mathcal{G}_n\) always contains (at least) the cycles describing the following configurations, which are in the basin of attraction of \(1^L\),\(L\geq 5\):

  • \(1^L\), for any \(L\geq 5\);

  • \((10)^{L/2}\) and \((01)^{L/2}\), for even \(L\)

  • \((1100)^{L/4}\), \((1001)^{L/4}\), \((0011)^{L/4}\) and \((0110)^{L/4}\), for \(L=4k\), for some integer \(k\geq 2\).

  Such cycles will be referred to as the trivial failing cycles of \(f^n\).

  For \(783\) out of the \(789\) rules in class \(C\), there is \(1\leq n_1\leq 9\) such that the only cycles in \(\mathcal{G}_{n_1}\) are the trivial failing cycles of \(f^{n_1}\), therefore, for any configuration apart from the ones described above, there is at least one block of three adjacent 0s in its image under \(f^{n_1}\).

  Table 4 shows the number of rules in class C satisfying property C1) for different values of \(n_1\).

  Table 4: Number of rules in Class C such that \(n_1\) is the smallest integer for which \(f^{n_1}\) satisfies the property C1).

  \(n_1\)	1	2	3	4	5	6	7	8	9	Total
  # of rules	32	263	331	110	33	10	2	0	2	783

• Property C2): Property C2) was achieved for \(714\) out of the \(789\) rules in class C for some \(1\leq n_2 \leq 5\).

  Let \(W_{(l,i)}=\{b=(b_1,\cdots,b_l)\in\{0,1\}^l:b_ib_{i+1}b_{i+2}=000\}\) for integers \(l,i\) with \(1\leq i\leq l-2\) and \(l\geq 3\). That is, \(W_{(l,i)}\) is the set of all binary blocks of length \(l\) containing \(000\) as a sub-block in position \(i\).

  For every \(f\) in class C we checked whether or not there were integers \(n_2\) and \(i_3\) such that, for every block \(z=(z_1,\cdots,z_{4n_2+4})\in X_{(4n_2+4,i_3)}\), the following condition was satisfied: \[\left(f^{n_2}(z_1,\cdots,z_{4n_2+4}),f^{n_2}(z_2,\cdots,z_{4n_2+2}),f^{n_2}(z_3,\cdots,z_{4n_2+3}),f^{n_2}(z_3,\cdots,z_{4n_2+3})\right)=(0,0,0,0)\]

  This is analogous to condition \(B2)\) (expansion of 00s) in class B, and shows that, for every triple of adjacent cells in state 0 in a configuration, there is a quadruple of adjacent cells in state 0 in its image under \(f^{n_2}\), possibly displaced by \(i_3\) positions to the left or to the right (depending on \(i_3\) being positive or negative) from the position of \(000\) in the original configuration.

  Table 5 shows the number of rules in class C satisfying such a condition for different values of \(n_2\).

  Table 5: Number of rules in Class C such that \(n_2\) is the smallest integer for which \(f^{n_2}\) satisfies the condition C2).

  \(n_2\)	1	2	3	4	5	Total
  # of rules	468	114	26	61	45	714

• Properties C3) and C4): For every \(f\) in class C, properties C3) and C4) were readily verified by checking the images of \((0,0,1,1,0), (0,1,1,0,0),(1,1,0,0,1), (1,0,0,1,1), (0,1,0,1,0),(1,0,1,0,1),(0,0,0,0,0)\) and \((1,1,1,1,1)\) under \(f\).

Out of the \(789\) rules in class C, \(80\) do not satisfy \(C1)\) or \(C2)\) for the tested values, therefore, the results above show that at least \(709\) rules in \(C\) solve the same decision problem for all \(L\geq 5\) that they solved for \(5 \leq L \leq 20\).

5 Concluding remarks↩︎

5.1 Retrospective and prospects↩︎

Achieving solutions of decision problems by distributed consensus in cellular automata with finite configurations is a challenging endeavour because they have to be valid for any configuration size. However, this research direction is clearly motivating insofar as it can lead to a way of solving a global problem by means of a totally local fashion, in consensus with all the parts concerned.

In tune with that, after a reappraisal of the related results available in the literature for binary one-dimensional CAs with radius 2, we significantly extended what was known about the possible decision problems in the space, by settling the matter on many more rules and at the same time identifying a number of other candidate decision problems. More precisely, a single problem had been characterised (the one corresponding to our Class A) and associated to only 1,121 rules, a number that increased here to 27,251. The other two problems we analysed, related to Classes B and C, led to settle 12,294 and 709 rules for each class, respectively. So, out of the 54,928 radius-\(2\) consensus rules obtained for \(5 \leq L \leq 20\), at least 40,254 rules (representing, approximately, \(73.3 \%\) of the total amount of potential consensus rules) really do solve decision problems for configurations of any length \(L \geq 5\).

As for the 9,229 uncharacterised rules, recall that, as mentioned earlier, while some of them may turn out not to be decision problems at all, as they might be filtered out for configuration sizes larger than \(L=20\), other rules remain as true candidates, related to additional decision problems not analysed here, or even to the decision problems of the Classes A, B or C, which we could not establish due to a possible partiality of our characterisation.

It is also worth remarking that the problems related to Classes A, B and C, as well as those that might be eventually associated to the remaining rules, have (or would have, for the latter set) a description that is biased by the rule we currently take as reference in its dynamical equivalence class, namely, the rule with the smallest number in the class (which is made up by the rule itself and the related symmetrical rules due to negation, reflection or both). This means, for instance for the rules in Class A, that the corresponding negated rules would have \(1^L\) as the main fixed point (the one with almost all configurations converging to it), not to \(0^L\), as in Class A. Nevertheless, these other problems are essentially the same up to negation, reflection or both.

In contrast to the standard synchronous/parallel update, deterministic block sequential updates refer to the form of asynchronism achieved by partitioning a configuration and assigning an update priority to each of its blocks, from 1 up to the number of blocks [9]; in this sense, the synchronous update is simply the special case where the partition has a single block with priority 1. It is known that any fixed point is invariant to any block sequential update, which means that any existing fixed point in the synchronous case should also exist in any other asynchronous update. Consequently, if a rule is to be truly thought to be solving a decision problem by distributed consensus, its attractors can only be the two fixed points \(0^L\) and \(1^L\), regardless of the block sequential update employed. So, by subjecting the action of the remaining 14,674 rules to all possible deterministic block sequential updates from increasing sizes \(L\), a further filtering process can be carried out towards likelier consensus type rules, since any rule displaying a new attractor for some asynchronous update cannot be granted the consensus type status and, therefore, can be discarded. This is a sensible supplemental procedure to the filtering done here, as this would help reinforce the status of consensus type rule to the remaining candidates.

Notwithstanding the difficulty of formally charactering the dynamics of the rules involved, the actual decision problems concerned are still very simple, as showed. So, consensus type rules solving more elaborate and interesting problems must be searched among the remaining 14,674 radius-\(2\) rules, as discussed below and in the Appendix. And characterising them undoubtedly constitutes the natural follow-up to the present work.

5.2 A view on all candidate decision problems of the space↩︎

In the Appendix we provide a complete listing of the 54,928 rules that were obtained out of the filtering process carried out to identify candidate consensus rules in the CA space we analysed. Each piece of data refers to a pattern containing the number of configurations associated to the fixed point \(1^L\), for every size \(L\) in ascending order from \(L=5\) to \(L=20\), and the amount of rules displaying the corresponding pattern. In total we identified 485 distinct patterns, which are shown in lexicographic order.

For instance, with respect to the decision problems we characterised here, the pattern {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1} corresponds to all 30,230 rules in Class A and {1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3} refers to all 14,680 rules in Class B. As for the rules in Class C, the pattern {1, 3, 1, 7, 1, 3, 1, 7, 1, 3, 1, 7, 1, 3, 1, 7} refers to 1,223 rules, which includes all 709 characterised Class C rules, but also others that, as mentioned earlier, might still be solving the Class C decision problem but our characterisation was insufficient to account for them; rules that might be solving different decision problems; or others that would not be solving a decision problem at all, but were not filtered out within the configuration sizes the filtering process relied upon. By the way, these three possibilities apply to all 14,674 rules not yet accounted for.

Among them, some rules may be quite likely very easy to characterise because they exhibit a straightforward pattern, as is the case for the 9 rules associated to pattern {31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575}, which clearly refers to basins of attraction with \(2^L-1\) configurations leading to the fixed point point \(1^L\), analogously to Class A. Equally easy seems the characterisation of the 23 rules linked to the pattern {31, 61, 127, 253, 511, 1021, 2047, 4093, 8191, 16381, 32767, 65533, 131071, 262141, 524287, 1048573}, which additionally imply that the configurations \((01)^{L/2}\) and \((10)^{L/2}\) converge to \(1^L\), in all even-sized configurations, analogously to what happens in Class B. By inspecting the list of patterns, various others also seem to be subject of an easy characterisation, such as the 342 rules associated to {1, 3, 1, 11, 1, 3, 1, 11, 1, 3, 1, 11, 1, 3, 1, 11}, the 236 rules associated to {1, 9, 1, 3, 1, 3, 1, 9, 1, 3, 1, 3, 1, 9, 1, 3}, etc.

But while the simple characterisations are suggestive of overly simple related decision problems, many other rules might be leading to possibly more interesting and relevant problems, even though requiring more sophisticated analyses. This might be the case of 258 candidate problems which are associated to a single rule each. Or, more precisely, the case, for instance, of the 30 rules corresponding to the pattern {21, 39, 71, 131, 241, 443, 815, 1499, 2757, 5071, 9327, 17155, 31553, 58035, 106743, 196331}, which seems to comply with the integer sequence A001644 [10], which for \(L\geq 3\), \(a(L)\) is the number of cyclic sequences consisting of \(L\) 0s and 1s that do not contain three consecutive 1s, provided the positions of the 0s and 1s are fixed on a circle. Many surprises such as this is quite likely hidden in the list of patterns, waiting to be uncovered.

Acknowledgements↩︎

This work has been partially funded by the HORIZON-MSCA-2022-SE-01 project 101131549 “Application-driven Challenges for Automata Networks and Complex Systems (ACANCOS)”, and by the STIC-AmSud 22-STIC-02 project “Consensus Cellular Automata Algorithms and Tie-Majority Classification” (CAMA) provided by CAPES 88881.694458/2022-01, ANID and MEAE). P.P.B. additionally thanks CNPq for the research grant PQ 303356/2022-7, and CAPES for Mackenzie-PrInt research grant no./2018-00. K.P. additionally thanks project ANR-24-CE48-7504 ALARICE. E.G. and M.M-M. additionally thanks project FONDECYT/ANID Regular 1250984.

↩︎

Here we provide a listing of all 54,928 rules that were obtained out of the filtering process carried out to identify candidate consensus rules in the CA space we analysed. Each piece of data refers to a pattern containing the number of configurations associated to the fixed point \(1^L\), for every size \(L\) in ascending order from \(L=5\) to \(L=20\), and the amount of rules displaying the corresponding pattern. In total we identified 485 distinct patterns, shown here in lexicographic order, for easier reference. The corresponding rules in each of them are omitted here, but are all available upon request.

References↩︎