Computational Universality of Fungal Sandpile Automata

Fungi grow as networks of hyphae—filamentous structures partitioned by septa that regulate and redirect the flow of information and nutrients. This biological mechanism suggests a simple but powerful idea: what happens if, in a cellular automaton, we deliberately restrict the direction in which information can propagate? Motivated by this question, we introduce fungal automata: two-dimensional cellular automata in which, at each time step, information is allowed to flow only horizontally (H) or vertically (V), according to a prescribed update word in the set {H, V}*. Under the von Neumann neighborhood, each directional cut reduces the dynamics to one dimension—yet the global behavior remains inherently two-dimensional. Within this framework, we revisit one of the most classical models of discrete dynamics: the chip-firing game, or sandpile automaton. The central result is striking. Despite the severe directional constraints, the fungal sandpile automaton can simulate arbitrary Boolean circuits. In other words, it is computationally universal. This is particularly remarkable because, for the standard two-dimensional sandpile automaton with the von Neumann neighborhood, it is still unknown whether arbitrary Boolean circuits can be simulated. Paradoxically, introducing directional cuts—thus fragmenting the dynamics —makes universality provable. Initially, universality was obtained for the periodic word H4V4, that is applying the horizontal restriction four consecutive times, followed by four consecutive applications of the vertical restriction (HHHHVVVV). Later work showed that the much simpler alternation HV already suffices. Most recently, we proved a robustness theorem: any nontrivial periodic word containing at least one H and one V yields universality. Thus, even under drastic anisotropic constraints, computation persists. Directional fragmentation does not destroy complexity—it reorganizes it. I will discuss these results, their proof ideas, recent advances on totalistic fungal automata, and some open problems. References • E. Goles, M.-A. Tsompanas, A. Adamatzky, M. Tegelaar, H. A. Wosten, and G. J. Martínez. “Computational universality of fungal sandpile automata.” Physics Letters A 384.22 (2020), 126541. • A. Modanese and T. Worsch. “Embedding arbitrary Boolean circuits into fungal automata.” Algorithmica (2024), 1–23.