Solving decision problems by distributed consensus with one-dimensional, binary, radius-$2$ cellular automata over cyclic configurations
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911227497676800 |
|---|---|
| author | Ruivo, Eurico Balbi, Pedro Paulo Perrot, Kévin Montalva-Medel, Marco Goles, Eric |
| author_facet | Ruivo, Eurico Balbi, Pedro Paulo Perrot, Kévin Montalva-Medel, Marco Goles, Eric |
| contents | Probing the ability of automata networks to solve decision problems has received a continuous attention in the literature, and specially with the automata reaching the answer by distributed consensus, i.e., their all taking on a same state, out of two. In the case of binary automata networks, regardless of the kind of update employed, the networks should display only two possible attractors, the fixed points $0^L$ and $1^L$, for all cyclic configurations of size $L$. A previous investigation into the space of one-dimensional, binary, radius-2 cellular automata identified a restricted subset of rules as potential solvers of decision problems, but the reported results were incomplete and lacked sufficient detail for replication. To address this gap, we conducted a comprehensive reevaluation of the entire radius-2 rule space, by filtering it with all configuration sizes from 5 to 20, according to their basins of attraction being formed by only the two expected fixed points. A set of over fifty-four thousand potential decision problem solvers were then obtained. Among these, more than forty-five thousand were associated with 3 well-defined decision problems, and precise formal explanations were provided for over forty thousand of them. The remaining candidate rules suggest additional problem classes yet to be fully characterised. Overall, this work substantially extends the understanding of radius-2 cellular automata, offering a more complete picture of their capacity to solve decision problems by consensus. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_01040 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Solving decision problems by distributed consensus with one-dimensional, binary, radius-$2$ cellular automata over cyclic configurations Ruivo, Eurico Balbi, Pedro Paulo Perrot, Kévin Montalva-Medel, Marco Goles, Eric Discrete Mathematics Probing the ability of automata networks to solve decision problems has received a continuous attention in the literature, and specially with the automata reaching the answer by distributed consensus, i.e., their all taking on a same state, out of two. In the case of binary automata networks, regardless of the kind of update employed, the networks should display only two possible attractors, the fixed points $0^L$ and $1^L$, for all cyclic configurations of size $L$. A previous investigation into the space of one-dimensional, binary, radius-2 cellular automata identified a restricted subset of rules as potential solvers of decision problems, but the reported results were incomplete and lacked sufficient detail for replication. To address this gap, we conducted a comprehensive reevaluation of the entire radius-2 rule space, by filtering it with all configuration sizes from 5 to 20, according to their basins of attraction being formed by only the two expected fixed points. A set of over fifty-four thousand potential decision problem solvers were then obtained. Among these, more than forty-five thousand were associated with 3 well-defined decision problems, and precise formal explanations were provided for over forty thousand of them. The remaining candidate rules suggest additional problem classes yet to be fully characterised. Overall, this work substantially extends the understanding of radius-2 cellular automata, offering a more complete picture of their capacity to solve decision problems by consensus. |
| title | Solving decision problems by distributed consensus with one-dimensional, binary, radius-$2$ cellular automata over cyclic configurations |
| topic | Discrete Mathematics |
| url | https://arxiv.org/abs/2510.01040 |