Universality Frontier for Asynchronous Cellular Automata
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908598225862656 |
|---|---|
| author | Baburin, Ivan Cook, Matthew Grötschla, Florian Plesner, Andreas Wattenhofer, Roger |
| author_facet | Baburin, Ivan Cook, Matthew Grötschla, Florian Plesner, Andreas Wattenhofer, Roger |
| contents | In this work, we investigate the computational aspects of asynchronous cellular automata (ACAs), a modification of cellular automata in which cells update independently, following an asynchronous schedule. We introduce flip automata networks (FAN), a simple modification of automata networks that remain robust under any asynchronous update schedule. We show that asynchronous automata can efficiently simulate their synchronous counterparts with a linear memory overhead, which improves upon the previously established quadratic bound. Additionally, we address the universality gap for (a)synchronous cellular automata -- the boundary separating universal and non-universal automata, which is still not fully understood. We tighten this boundary by proving that all one-way asynchronous automata lack universal computational power. Conversely, we establish the existence of a universal 6-state first-neighbor automaton in one dimension and a 3-state von Neumann automaton in two dimensions, which represent the smallest known universal constructions to date. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_05989 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Universality Frontier for Asynchronous Cellular Automata Baburin, Ivan Cook, Matthew Grötschla, Florian Plesner, Andreas Wattenhofer, Roger Formal Languages and Automata Theory In this work, we investigate the computational aspects of asynchronous cellular automata (ACAs), a modification of cellular automata in which cells update independently, following an asynchronous schedule. We introduce flip automata networks (FAN), a simple modification of automata networks that remain robust under any asynchronous update schedule. We show that asynchronous automata can efficiently simulate their synchronous counterparts with a linear memory overhead, which improves upon the previously established quadratic bound. Additionally, we address the universality gap for (a)synchronous cellular automata -- the boundary separating universal and non-universal automata, which is still not fully understood. We tighten this boundary by proving that all one-way asynchronous automata lack universal computational power. Conversely, we establish the existence of a universal 6-state first-neighbor automaton in one dimension and a 3-state von Neumann automaton in two dimensions, which represent the smallest known universal constructions to date. |
| title | Universality Frontier for Asynchronous Cellular Automata |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2502.05989 |