Volume 33, Issue 1 (2024)

Realizability of Parity Logic in Finite Cellular Automata

Celestine P. Lawrence
Bernoulli Institute and Groningen Cognitive Systems and Materials Center (CogniGron)
University of Groningen
9700 AB, Groningen, Netherlands
c.p.lawrence@rug.nl

Abstract

We investigate a range-4 cellular automaton that was designed and (falsely) proven to realize the parity logic for any odd input size N. We find that it fails to perform at N=13 and provide a Boolean bottleneck conjecture to redirect research efforts.

Keywords: finite cellular automata; Boolean parity; Boolean bottleneck; compression; state transition diagrams; functional graphs  

Cite this publication as:
C. P. Lawrence, “Realizability of Parity Logic in Finite Cellular Automata,” Complex Systems, 33(1), 2024 pp. 125–132.
https://doi.org/10.25088/ComplexSystems.33.1.125