On the Separate Even- and Odd-parity Problems for Cellular Automata
Anna Nenca, Barbara Wolnik and Bernard De Baets
The classical parity problem asks for a cellular automaton that can classify any initial configuration (with an odd number of cells) based on the parity of 1s. The challenge of this task lies in achieving this classification by using local information only, since, due to the nature of cellular automata, each cell’s next state depends only on its neighbors’ states. Therefore, the parity problem is seen as one of the key challenges for understanding the computational capabilities of CAs. It is already known that there exists a cellular automaton that solves the parity problem. It requires as many as nine cells in its neighborhood, and it is not known whether there exists one that requires fewer cells. However, during our research in this area, another question popped up: if one would reduce the requirements in the classical parity problem “by half”, i.e., solving the problem only for all odd configurations or for all even configurations, would it become a much easier task for cellular automata? This paper presents the results of our investigations in this direction.
Keywords: One-dimensional cellular automata, binary cellular automata classification problem, parity problem, even parity, odd parity