Non-trivial automata networks do exist that solve the global majority problem with the local majority rule
Pedro Paulo Balbi, Kévin Perrot, Marius Rolland, Eurico Ruivo · 2026
Read Non-trivial automata networks do exist that solve the global majority problem with the local majority rule by Pedro Paulo Balbi, Kévin Perrot, Marius Rolland, Eurico Ruivo (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-19472.txt.
Description
Balbi and co-authors show that the plain local majority rule can solve the global majority task on some networks. The task asks binary cells to settle on the true overall majority by local means alone. For classic cellular automata with wrap-around edges, no rule can do it. The team studies automata networks that use only this local update. They find non-trivial cases where the rule does solve the task. The work explains what marks those cases apart.
Catalog record
| CREATOR | Pedro Paulo Balbi, Kévin Perrot, Marius Rolland, Eurico Ruivo |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 51417 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.19472