Embedding Boolean circuits into fungal automata with arbitrary update sequences
E. Goles , A. Modanese , M. Ríos-Wilson , D. Ruiz-Tala and T. Worsch · 2026
Read Embedding Boolean circuits into fungal automata with arbitrary update sequences by E. Goles , A. Modanese , M. Ríos-Wilson , D. Ruiz-Tala and T. Worsch (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-2602-19477.txt.
Description
Sandpile automata model particles diffusing in space, and predicting their parallel evolution has resisted sorting for two-dimensional cases. Eric Goles and four co-authors study fungal automata, a spin-off where diffusion moves sideways or up-down according to an update scheme. Earlier work proved the forecast P-complete for the update schemes H4V4 and then the simpler HV scheme.
The present paper fills the gaps, proving prediction P-complete for any update sequence. Any Boolean circuits can be embedded into fungal models with any update sequences, closing the sorting problem. Readers get a completeness result that settles, for every scheme at once, how hard predicting these models can be.
Catalog record
| CREATOR | E. Goles , A. Modanese , M. Ríos-Wilson , D. Ruiz-Tala and T. Worsch |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 69 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-19477