EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Cellular automata can really solve the parity problem

Barbara Wolnik, Anna Nenca, Pedro Paulo Balbi, Bernard De Baets

Natural Computing · 2026-12 · 25 (2)

DOI: 10.1007/s11047-026-10083-8 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Natural Computing, online erschienen am 22.08.2026. Verfasst von Barbara Wolnik und 3 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 12 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Narodowe Centrum Nauki, Conselho Nacional de Desenvolvimento Científico e Tecnológico, Coordenação de Aperfeiçoamento de Pessoal de Nível Superior.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 proposed solution to this problem with a single rule was given more than 10 years ago (and coined BFO rule after the authors’ initials). However, three years later its authors realised that the rule would fail for a specific configuration and proposed a computationally sound fix, but a proof could not be worked out. Here we provide a fix to that failing rule along with a full proof, therefore reassuring that a single-rule solution to the problem really does exist.

Förderung

  • Narodowe Centrum Nauki
  • Conselho Nacional de Desenvolvimento Científico e Tecnológico
  • Coordenação de Aperfeiçoamento de Pessoal de Nível Superior

Zitieren

APA

Wolnik, B., Nenca, A., Balbi, P. P., & Baets, B. D. (2026). Cellular automata can really solve the parity problem. Natural Computing, 25(2). https://doi.org/10.1007/s11047-026-10083-8

Vancouver

Wolnik B, Nenca A, Balbi PP, Baets BD. Cellular automata can really solve the parity problem. Natural Computing. 2026;25(2). doi:10.1007/s11047-026-10083-8

BibTeX
@article{Wolnik2026,
  author = {Wolnik, Barbara and Nenca, Anna and Balbi, Pedro Paulo and Baets, Bernard De},
  title = {Cellular automata can really solve the parity problem},
  journal = {Natural Computing},
  year = {2026},
  volume = {25},
  number = {2},
  doi = {10.1007/s11047-026-10083-8}
}
Kostenlos starten →