Cellular automata can really solve the parity problem
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915607809622016 |
|---|---|
| author | Wolnik, Barbara Nenca, Anna Balbi, Pedro Paulo De Baets, Bernard |
| author_facet | Wolnik, Barbara Nenca, Anna Balbi, Pedro Paulo De Baets, Bernard |
| contents | 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 known solution to this problem with a single rule was given by Betel, de Oliveira and Flocchini (coined BFO rule after the authors' initials). However, three years later the authors of the BFO rule realised that the rule would fail for some specific configuration and proposed a computationally sound fix, but a proof could not be worked out. Here we provide another fix to the BFO rule along with a full proof, therefore reassuring that a single-rule solution to the problem really does exist. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_08684 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Cellular automata can really solve the parity problem Wolnik, Barbara Nenca, Anna Balbi, Pedro Paulo De Baets, Bernard Dynamical Systems Formal Languages and Automata Theory 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 known solution to this problem with a single rule was given by Betel, de Oliveira and Flocchini (coined BFO rule after the authors' initials). However, three years later the authors of the BFO rule realised that the rule would fail for some specific configuration and proposed a computationally sound fix, but a proof could not be worked out. Here we provide another fix to the BFO rule along with a full proof, therefore reassuring that a single-rule solution to the problem really does exist. |
| title | Cellular automata can really solve the parity problem |
| topic | Dynamical Systems Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2501.08684 |