Universality Frontier for Asynchronous Cellular Automata
Ivan Baburin, Matthew Cook, Florian Grötschla, Andreas Plesner, Roger Wattenhofer · 2025
Read Universality Frontier for Asynchronous Cellular Automata by Ivan Baburin, Matthew Cook, Florian Grötschla, Andreas Plesner, Roger Wattenhofer (2025) 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-2502-05989.txt.
Description
Ivan Baburin and co-authors probe the power limits of asynchronous cellular automata in this 2025 paper. In these grids, cells update on their own clocks rather than in lockstep. Which such systems can compute anything at all was only partly known.
The team defines flip automata networks that stay sound under any update order. They show asynchronous grids can mimic synchronous ones with only linear extra memory, beating an older square bound. One-way asynchronous automata, they prove, can never be universal computers. Yet a six-state line automaton and a three-state plane automaton both reach full power. Those are the smallest universal builds of their kind known so far.
Catalog record
| CREATOR | Ivan Baburin, Matthew Cook, Florian Grötschla, Andreas Plesner, Roger Wattenhofer |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 86 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-05989