Cellular automata can really solve the parity problem

Basic Information

• Paper ID: 2501.08684
• Title: Cellular automata can really solve the parity problem
• Authors: Barbara Wolnik (University of Gdańsk), Anna Nenca (University of Gdańsk), Pedro Paulo Balbi (Universidade Presbiteriana Mackenzie), Bernard De Baets (Ghent University)
• Classification: math.DS (Dynamical Systems), cs.FL (Formal Languages and Automata Theory)
• Publication Date: January 2025 (arXiv v2: November 10, 2025)
• Paper Link: https://arxiv.org/abs/2501.08684v2

Abstract

This paper investigates the parity problem in cellular automata (CA)—a classical problem concerning the determination of global properties of binary sequences through local processing. In its standard formulation, a one-dimensional cellular automaton rule should be capable of processing arbitrary odd-length cyclic configurations and converging the lattice to homogeneous fixed points of all 0s (even number of 1s) or all 1s (odd number of 1s). The BFO rule (named after Betel, de Oliveira, and Flocchini) was previously the only known single-rule solution to this problem, but was later found to fail on specific configurations. This paper provides an alternative correction to the BFO rule with complete proof, confirming that single-rule solutions indeed exist.

Research Background and Motivation

Core Problem

The parity problem requires determining the parity of the number of 1s in an entire binary sequence through purely local operations (where each cell can only observe its neighbors), and achieving distributed consensus such that all cells eventually converge to:

• All 0s if the number of 1s is even
• All 1s if the number of 1s is odd

Problem Significance

1. Theoretical Benchmark Value: The parity problem serves as an important benchmark for testing the capabilities and limitations of fully localized distributed computation
2. Computational Complexity: It has been proven that any solution requires a neighborhood of at least 7 cells (radius at least 3)
3. Distributed Consensus: Represents a typical challenge in achieving global agreement through local interactions in automaton networks

Limitations of Existing Approaches

Although multiple alternative approaches exist (non-uniform cellular automata, different rules at different time steps, asynchronous updates, etc.), single-rule solutions for standard synchronous cellular automata are limited to the BFO rule. However:

• The original BFO rule proposed in 2013 was found to fail on configuration 0001110101001 (length 13) in 2016
• The authors proposed a corrected BFOm rule and computationally verified all configurations up to length 31, but failed to provide mathematical proof
• The lack of rigorous proof cast doubt on the existence of single-rule solutions

Paper Motivation

To provide a new corrected version of the BFO rule (modifying T7 and T8 active transitions) with complete mathematical proof, confirming the existence of single-rule solutions and refuting recent impossibility conjectures.

Core Contributions

1. Corrected the BFO Rule: Fixed defects in the original rule through mirror reflection of T7 and T8 active transitions
2. Provided Complete Rigorous Proof: Delivered the first complete mathematical proof of the corrected BFO rule's correctness
3. Innovative Proof Technique: Introduced a novel proof method based on "switches" and "boxes," differing from the original de Bruijn graph approach
4. Confirmed Existence: Definitively proved that single-rule cellular automaton solutions to the parity problem do exist

Detailed Methodology

Task Definition

Input: Odd-length cyclic binary configuration $x \in X_{odd} = \bigcup_{n=1}^{\infty} \{0,1\}^{2n-1}$

Output: Homogeneous configuration after finite evolution steps

• If $Par(x) = 0$ (even number of 1s), converge to all 0s
• If $Par(x) = 1$ (odd number of 1s), converge to all 1s

Constraints:

• Use only a single local rule $f: \{0,1\}^9 \to \{0,1\}$ (radius 4)
• Synchronous update of all cells
• Periodic boundary conditions (cyclic lattice)

BFO Rule Architecture

Basic Mechanism

The BFO rule's design principle is to reduce the number of 0-blocks and 1-blocks in configurations through:

1. 1-block rightward propagation: Moving 2 cells per iteration
2. 0-block leftward propagation: Synchronized with 1-block propagation
3. Stopping condition: Ensuring both trends can coexist

Active Transitions (AT)

The rule is defined through 512 state transitions, but only requires specifying active transitions that change the center cell state (Table 1):

Key Corrected Transitions:

• T7: [•001010••] → center bit changes from 1 to 0
• T8: [••001010•] → center bit changes from 1 to 0

The original version incorrectly defined these patterns as variants of [•••0110••]; the corrected version fixes this error through mirror reflection.

Seven Pairs of AT and Their Functions

The rule defines 7 pairs of active transitions (Tables 2-3):

Technical Innovation Points

1. Switch Concept

Definition: A quantitative measure of configuration non-homogeneity

• r-switch (regular switch): Position $i$ where $x_i \neq x_{i+1}$ and neither belongs to any box
• b-switch (box switch): Position $i$ where $x_{i+1}x_{i+2}$ is a box

Key Properties:

• Configuration is homogeneous if and only if $s(x) = 0$ (Proposition 1)
• Switch count is monotonically decreasing: $s(F(x)) \leq s(x)$ (Proposition 2)

2. Box Patterns

Definition: Pattern 01 preceded by 1 and followed by 00, i.e., $x_{i-1}=1, x_ix_{i+1}=01, x_{i+2}x_{i+3}=00$

Functions of boxes:

• Identify configuration parts requiring special treatment
• b-switches associate with boxes with broader coverage
• Corrected T7,8 specifically handle patterns containing boxes

3. Ordered Blocks

Definition (Definition 4): A block $x_ix_{i+1}...x_{i+2k+1}$ satisfying three conditions:

• (C1) All two-symbol blocks belong to {00, 01, 11} (no 10)
• (C2) Begins with 01 but does not end with 01
• (C3) If ending with 11, must be followed by 0

Key Lemma:

• Ordered block length does not exceed configuration length plus 1 (Lemma 8)
• If $x \in X_s$ (configurations with constant switch count), then $x$ contains no ordered blocks (Proposition 4)

4. Proof Strategy

Three-Step Proof Framework:

Step 1: Prove switch count is monotonically decreasing (Section 3)

• Analyze the effect of 7 AT pairs on switches one by one
• Prove no AT pair generates new switches
• Certain AT pairs (e.g., T5,6 acting on $D_5,6^r$) reduce switch count

Step 2: Characterize configurations with constant switch count (First half of Section 4)

• Define set $X_s = \{x \in X_{odd} | s(F^t(x)) \text{ is constant}\}$
• Prove configurations in $X_s$ do not contain specific domain variants (e.g., $D_{5,6}^r, D_{7,8}^r$, etc.)
• Prove configurations in $X_s$ contain no ordered blocks (Proposition 4, key result)

Step 3: Complete main theorem (Theorem 3)

• Assume non-homogeneous configuration $x$ such that $\{F^t(x)\}$ never becomes homogeneous
• Then there exists $t_0$ such that $s(F^{t_0}(x))$ is constant, i.e., $F^{t_0}(x) \in X_s$
• But non-homogeneous configurations in $X_s$ can only apply T1,2 or T3,4
• These two AT pairs increase the number of 1s by 2 per step, contradicting finite length

Experimental Setup

Verification Method

This paper primarily provides mathematical proof, with computational verification as auxiliary:

• The corrected rule successfully tested on all initial configurations of odd lengths 3 to 29
• The original BFOm rule (previously proposed by the authors but unproven) tested up to length 31

Case Analysis

Failing Configuration: x = 0001110101001 (length 13)

• Original BFO Rule: Returns to initial configuration at $t=13$ (periodic failure)
• Corrected BFO Rule: Converges to all 0s at $t=13$ (Figure 1)

Detailed Evolution Example (Figure 2): Configuration x = 0000010111001011111

• Initial switch count $s(x) = 8$
• Switches progressively move and disappear
• Reaches all 0s at step 27, $s(F^{27}(x)) = 0$

Experimental Results

Main Results

Theorem 3 (Main Theorem): The corrected BFO rule solves the parity problem

Proof Completeness:

• All possible AT pair combinations analyzed (Sections 3.1-3.6)
• All boundary cases (domain overlap, special configurations) considered
• Proof spans approximately 20 pages with detailed case analysis

Key Lemma Verification

Lemmas 1-7: Verify properties of each AT pair one by one

• Lemmas 1,2: T1,2 and T3,4 generate no new switches; reduce switches when merging 1-blocks
• Lemma 3: T5,6 generates no new switches; reduces switches when acting on $D_{5,6}^r$
• Lemma 4: T7,8 generates no new switches; reduces switches when acting on $D_{7,8}^r$
• Lemmas 5-7: Corresponding properties for T9,10, T9,11, T9,12

Proposition 2: Sequence $(s(F^t(x)))_{t=0}^{\infty}$ is monotonically decreasing

Proposition 4 (Key): If $x \in X_s$, then $x$ contains no ordered blocks

• Proof by contradiction, assuming shortest-length configuration with longest ordered block
• Analyze all possible cases at ordered block end (ending with 11, ending with 00, etc.)
• Eliminate all possibilities one by one, deriving contradiction

Theoretical Guarantees

Theorem 1: BFO rule preserves parity (proven in original paper; correction does not affect this)

Theorem 2: The only fixed points are homogeneous configurations (proven in original paper)

Related Work

Other Solutions to the Parity Problem

1. Evolutionary Search Methods

• Wolz & de Oliveira (2008): Using evolutionary algorithms to search rule space
• Found highly effective but imperfect rules

2. Non-standard Cellular Automata Approaches

• Non-uniform CA (Sipper 1998): Different cells use different rules
• Temporal Rules (Lee et al. 2001; Martins & de Oliveira 2009): Different rules at different time steps
• Asynchronous Updates (Ruivo & de Oliveira 2019): Rule 150 perfectly solves under asynchronous updates
• Non-cyclic Graphs (Balbi et al. 2022, 2024; Faria et al. 2024): Solutions on specific connection graphs
• Stochastic Asynchronous (Fatès 2024): Random asynchronous update strategies

3. Theoretical Lower Bounds

• Nenca et al. (2024): Proved that 6-cell neighborhoods are insufficient to solve the parity problem
• Therefore, the BFO rule's radius 4 (9-cell neighborhood) approaches the theoretical lower bound

Unique Contributions of This Paper

• Only standard single-rule solution: In synchronous, uniform, deterministic settings
• Complete mathematical proof: Not relying on exhaustive computational verification
• Novel proof technique: Switch analysis method potentially applicable to other related problems

Conclusions and Discussion

Main Conclusions

1. Correction is Effective: Through mirror reflection of T7 and T8, the defects in the original BFO rule are fixed
2. Proof is Complete: Provides the first complete mathematical proof, confirming single-rule solutions exist
3. Method is Novel: Proof technique based on switches and ordered blocks is entirely new, differing from the original de Bruijn graph method
4. Conjecture Refuted: Definitively refutes Lawrence (2024)'s conjecture that single-rule solutions do not exist

Limitations

1. Rule Complexity

• Radius 4 (9-cell neighborhood) is relatively large
• 512 state transitions (though only 12 active transitions)
• Rule number is astronomically large (approximately $10^{154}$)

2. Convergence Time

• Paper does not analyze time complexity for convergence to homogeneous configuration
• Figure 2 example shows length-19 configuration requires 27 steps
• May exist configurations requiring $O(n^2)$ or higher time

3. Applicable Only to Odd Lengths

• By problem definition, even-length lattices do not apply
• All-1 configuration is not a fixed point for even lengths

4. Limitations of Proof Technique

• Proof highly dependent on specific structure of BFO rule
• Extensive case analysis, lacking elegance
• Difficult to generalize to other similar problems

Future Directions

1. Convergence Time Analysis

Study worst-case convergence time bounds

2. Simpler Rules

Seek rules with smaller radius (e.g., radius 3) or fewer state transitions

3. Improved Proof Methods

Develop more abstract and elegant proof techniques

4. Generalized Applications

Apply switch analysis method to other classification or consensus problems

5. Other Topologies

Investigate solutions on non-cyclic topologies (e.g., open boundaries)

In-Depth Evaluation

Strengths

1. Significant Theoretical Contribution

• Fills Critical Gap: The defect in the original BFO rule existed for nearly a decade; this paper finally provides complete solution
• Confirms Existence: Definitively proves single-rule solutions exist against background of impossibility conjectures
• Rigorous and Complete Proof: 20 pages of detailed proof considering all boundary cases

2. Methodological Innovation

• Novel Proof Technique: Concepts of switches and ordered blocks provide new perspective for analyzing CA dynamics
• Systematic Analysis: Individual analysis of 7 AT pairs demonstrates rigorous logical structure
• Generalizability: Proof framework potentially applicable to other CA classification problems

3. Solid Technical Details

• Exhaustive Case Analysis: Figures 3-14 demonstrate various domain overlaps and boundary cases
• Clear Symbolic Notation: Using $\ast, \circ, \prime, \diamond, \flat$ to mark switch movements aids tracking
• Tabulated Summaries: Tables 1-4 clearly present rule definitions and domain-image relationships

4. Clear Writing

• Logical Structure: Background → Method → Proof → Conclusion flows smoothly
• Precise Symbol Definition: All terms (boxes, switches, ordered blocks) precisely defined
• Sufficient Visualization: Figures 1-2 spacetime diagrams intuitively display rule behavior

Weaknesses

1. High Proof Complexity

• Numerous Cases: Sections 3.1-3.6 contain extensive subcases, difficult to grasp overall logic
• Technical Density: Requires careful tracking of each switch movement; high reading barrier
• Lack of High-Level Intuition: Why is this correction effective? Lacks intuitive explanation

2. Limited Experimental Verification

• Only Up to Length 29: While mathematical proof provided, computational verification range relatively limited
• No Performance Analysis: No statistical data on convergence time reported
• Missing Comparisons: No detailed comparison with BFOm rule (authors' previous correction)

3. Necessity of Correction Unclear

• Why Mirror Reflection: Paper states correction is "quite simple," but does not explain why this is correct direction
• Other Possible Corrections: Do other possible corrections exist? Is this correction unique?

4. Gap from Theoretical Lower Bound

• Radius 4 vs Radius 3: Known lower bound is 7 cells (radius 3); BFO uses 9 cells (radius 4)
• Optimality Unknown: Whether radius-3 solutions might exist remains undiscussed

5. Limited Practical Applicability

• Excessive Rule Complexity: 512 state transitions difficult to implement in practical systems
• Unclear Application Scenarios: Parity problem primarily theoretical benchmark; limited practical application value

Impact Assessment

Contribution to Field

• Benchmark Problem Resolution: Parity problem is classical CA problem; complete solution has milestone significance
• Methodological Contribution: Novel proof technique may inspire research on other CA classification problems
• Theoretical Confirmation: Confirms local processing can indeed solve certain global property determination problems

Practical Value

• Primarily Theoretical: Main contribution is theoretical; limited direct practical value
• Educational Value: Can serve as teaching case for CA theory and proof techniques
• Inspirational Significance: Provides insights for distributed consensus algorithm design

Reproducibility

• Complete Rule Definition: Table 1 provides all active transitions; in principle fully reproducible
• Astronomically Large Rule Number: Though complete Wolfram number provided, too large for direct use
• No Open-Source Code: Paper does not provide implementation code; readers must program verification themselves

Applicable Scenarios

1. Theoretical Research

• Theoretical analysis of CA classification problems
• Feasibility research on distributed consensus algorithms
• Investigation of relationship between local processing and global properties

2. Educational Applications

• Case studies in CA theory courses
• Teaching examples of formal proof methods
• Inspirational cases for distributed algorithm design

3. Methodological Reference

• Proof techniques for other CA problems
• Invariant analysis for dynamical systems
• Applications in symbolic dynamics

Key References

1. Betel et al. (2013): Original BFO rule proposal, Natural Computing 12(3):323-337
2. Betel et al. (2016): BFOm correction scheme (unpublished manuscript)
3. Nenca et al. (2024): Proof that 6-cell neighborhoods insufficient for parity problem
4. Lawrence (2024): Proposes impossibility conjecture for single-rule solutions (refuted by this paper)
5. Wolz & de Oliveira (2008): Evolutionary algorithm search for CA rules
6. Ruivo & de Oliveira (2019): Asynchronous solution using Rule 150

Summary

By correcting the T7 and T8 transitions of the BFO rule and providing complete mathematical proof, this paper confirms that single-rule cellular automaton solutions to the parity problem indeed exist. The innovative switch analysis method, though technically demanding, provides new perspective for analyzing CA dynamics. This represents important progress in CA theory; while practical value is limited, it holds milestone significance theoretically. The proof's completeness and rigor are commendable, though its complexity is high. Future work might explore more concise proofs or simpler rules.