Computational Universality of Fungal Sandpile Automata

Why It Matters

Demonstrating universal computation with biologically‑inspired sandpile automata opens fresh avenues for modeling natural information processing and deepens our understanding of computational complexity in low‑dimensional systems.

Key Takeaways

• Fungal-inspired sandpile automata simulate monotone logic gates efficiently.
• Alternating H‑V updates achieve universal computation in 2‑D.
• Crossover gadgets enable non‑planar circuit simulation within the model.
• Asynchronous updates break determinism, requiring strict synchronous scheduling.
• Predicting final states remains computationally hard for complex rule sets.

Summary

The talk introduces a novel cellular‑automaton framework inspired by fungal communication, where each cell’s compartment can be open or closed, allowing token flow across a von Neumann neighborhood. By treating the system as a sandpile model, the presenter demonstrates how simple token‑distribution rules generate wires and basic monotone gates such as AND and OR.

Key technical results show that iterating horizontal (H) and vertical (V) cuts—specifically H⁴V⁴ or even the simpler alternating HB pattern—suffices to simulate any monotone circuit, establishing computational universality in two dimensions. The construction includes crossover gadgets that let signals intersect without interference, overcoming the planar‑circuit limitation of earlier sandpile models.

Examples feature a four‑token signal traversing a wire, merging at an OR gate, and splitting at a crossover where a signal from the lower left exits at the upper right. Colleagues Modaneze and Thomas Wortsch later proved that the HB schedule alone can realize all monotone circuits, simplifying the original H⁴V⁴ scheme. The speaker also explores freezing automata, totalistic rules, and the difficulty of predicting steady states for non‑linear functions.

These findings bridge biological signaling concepts with theoretical computer science, offering a new universal computing substrate while highlighting open challenges such as asynchronous update effects and the complexity of state‑prediction algorithms.

Original Description

Eric Goles, University of Adolfo Ibáñez

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.

E. Goles, A. Modanese, M. Ríos-Wilson, D. Ruiz, T. Worsch. Embedding Boolean circuits into fungal automata with arbitrary H, V update sequences. Preprint (2024), to be submitted to Theoretical Computer Science.

C. Moore, M. Nilsson, The computational complexity of sandpiles, J. Statist. Phys. 96 (1999) 205 224

E. Goles, M. Margenstern, Sand pile as a universal computer, Internat. J. Modern Phys. C 7 (2) (1996) 113 122.

E. Goles, M. Margenstern, Universality of the chip firing game, Theoretical Computer Science 172 (1 2) (1997) 121 134.

A. Gajardo, E. Goles, Crossing information in two dimensional Sandpiles, Theoretical Computer Science, 369 (2006) 463-469.

Learn more, follow us on social media and check out our podcasts:

https://linktr.ee/sfiscience