Santa Fe Institute

Computational Universality of Fungal Sandpile Automata

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.