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

CREATORPedro Paulo Balbi, Kévin Perrot, Marius Rolland, Eurico Ruivo
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE51417
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.19472

Browse the full library · About the Tower of Babel