Computational universality of fungal sandpile automata

Eric Goles, Michail Antisthenis Tsompanas, Andrew Adamatzky, Martin Tegelaar, Han A.B. Wosten, Genaro J. Martínez

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

Hyphae within the mycelia of the ascomycetous fungi are compartmentalised by septa. Each septum has a pore that allows for inter-compartmental and inter-hyphal streaming of cytosol and even organelles. The compartments, however, have special organelles, Woronin bodies, that can plug the pores. When the pores are blocked, no flow of cytoplasm takes place. Inspired by the controllable compartmentalisation within the mycelium of the ascomycetous fungi we designed two-dimensional fungal automata. A fungal automaton is a cellular automaton where communication between neighbouring cells can be blocked on demand. We demonstrate computational universality of the fungal automata by implementing sandpile cellular automata circuits there. We reduce the Monotone Circuit Value Problem to the Fungal Automaton Prediction Problem. We construct families of wires, cross-overs and gates to prove that the fungal automata are P-complete.

Original languageEnglish
Article number126541
JournalPhysics Letters, Section A: General, Atomic and Solid State Physics
Volume384
Issue number22
DOIs
StatePublished - 6 Aug 2020
Externally publishedYes

Keywords

  • Computational universality
  • Fungi
  • Sandpile automata

Fingerprint

Dive into the research topics of 'Computational universality of fungal sandpile automata'. Together they form a unique fingerprint.

Cite this