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

CREATORE. Goles , A. Modanese , M. Ríos-Wilson , D. Ruiz-Tala and T. Worsch
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE69 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-19477

Browse the full library · About the Tower of Babel