Abstract Determining properties of an arbitrary binary sequence is a challenging task if only local processing is allowed. Among these properties, the determination of the parity of 1s by distributed consensus has been a recurring endeavour in the context of automata networks. In its most standard formulation, a one-dimensional cellular automaton rule should process any odd-sized cyclic configuration and lead the lattice to converge to the homogeneous fixed point of 0s if the parity of 1s is even and to the homogeneous fixed point of 1s, otherwise. The only proposed solution to this problem with a single rule was given more than 10 years ago (and coined BFO rule after the authors’ initials). However, three years later its authors realised that the rule would fail for a specific configuration and proposed a computationally sound fix, but a proof could not be worked out. Here we provide a fix to that failing rule along with a full proof, therefore reassuring that a single-rule solution to the problem really does exist.

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.

The parity problem is one of the best-known classification problems studied to examine the computational abilities of cellular automata . In this inverse problem , one is looking for a cellular automaton that can classify each initial configuration into one of two classes according to its parity. In the case of deterministic one-dimensional cellular automata , there exists a local rule that effectively solves the parity problem, but it is unknown whether it is the simplest possible rule. Specifically, it is known that a cellular automaton with a nine-cell neighborhood can solve the parity problem, whereas no cellular automaton with a five-cell neighborhood is capable of doing so. These findings have remained unimproved for the past 10 years. In this paper, we present novel tools that allow to narrow down the existing gap. With the help of these tools, we are able to demonstrate that there is no cellular automaton with a six-cell neighborhood capable of solving the parity problem.

In this paper, we study non-uniform elementary cellular automata on the infinite grid in the context of number conservation. These automata operate in a one-dimensional setting, where individual cells can employ distinct Wolfram rules for updating their states. The result is an exhaustive characterization of such number-conserving cellular automata. Until now, such a characterization was known only for finite grids, for which research hypotheses could be derived on the basis of computer experiments. It turns out that when considering number conservation for non-uniform cellular automata, the infinite grid cannot be treated as a limiting case of finite grids, i.e., there are number-conserving non-uniform cellular automata on the infinite grid that have no analogous counterpart on finite grids.

Abstract Little is known about the dynamics of k-ary (binary, ternary, quaternary, quinary, etc.) reversible number-conserving cellular automata. Here, we present some preliminary results in the case of seven states. In particular, we examine one of the most complex seven-state reversible and number-conserving rules and provide a full description of its dynamics.