Synchronous solution of the parity problem on cyclic configurations, with elementary cellular automaton rule 150, over a family of directed, non-circulant, regular graphs

The parity problem is one of the classical benchmarks for probing the computational ability of cellular automata. It refers to conceiving a rule to allow deciding whether the number of 1s in an arbitrary binary sequence is an odd or even number, without resorting to globally accessing the sequence. In its most traditional formulation, it refers to cyclic configurations of odd length, which, under the action of a cellular automaton, should converge to a fixed point of all cells in the 0-state, if the configuration initially has an even number of 1s, or to a fixed point of all cells in the 1-state, otherwise. It has been shown that the problem can be solved in this formulation, in particular by a rule alone. Here, we provide a synchronous solution to the problem, by relying upon elementary cellular automaton rule 150, the ele-mentary local parity rule, over a connection pattern among the cells defined by a family of directed, non-circulant, regular graphs. This represents the simplest synchronous solution currently known for cyclic configurations and, quite interestingly, being an instance of the solution of a non-trivial global problem by means of its local counterpart.(c) 2022 Elsevier Inc. All rights reserved.

Automated summary

The parity problem is a classical benchmark for studying the computational ability of cellular automata. This article presents a synchronous solution to the problem using elementary cellular automaton rule 150 and a connection pattern defined by a family of directed, non-circulant, regular graphs. This solution represents the simplest synchronous solution known for cyclic configurations and demonstrates solving a non-trivial global problem with a local counterpart.