Computational universality of fungal sandpile automata

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

doi:10.1016/j.physleta.2020.126541

Computational universality of fungal sandpile automata

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

^*Corresponding author for this work

Research output: Contribution to journal › Article › Academic › peer-review

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 language	English
Article number	126541
Pages (from-to)	1-8
Number of pages	8
Journal	Physics Letters, Section A: General, Atomic and Solid State Physics
Volume	384
Issue number	22
DOIs	https://doi.org/10.1016/j.physleta.2020.126541
Publication status	Published - 6 Aug 2020

Funding

AA, MT, HABW have received funding from the European Union's Horizon 2020 research and innovation programme FET OPEN “Challenging current thinking” under grant agreement No 858132 . EG residency in UWE has been supported by funding from the Leverhulme Trust under the Visiting Research Professorship grant VP2-2018-001 and from the project 1200006 , FONDECYT -Chile.

Keywords

Computational universality
Fungi
Sandpile automata

Access to Document

10.1016/j.physleta.2020.126541

1-s2.0-S0375960120304084-mainFinal published version, 712 KB

Cite this

@article{ad75660fa0e5438bb02f83a47274ef80,

title = "Computational universality of fungal sandpile automata",

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.",

keywords = "Computational universality, Fungi, Sandpile automata",

author = "Eric Goles and Tsompanas, \{Michail Antisthenis\} and Andrew Adamatzky and Martin Tegelaar and Wosten, \{Han A.B.\} and Mart{\'i}nez, \{Genaro J.\}",

year = "2020",

month = aug,

day = "6",

doi = "10.1016/j.physleta.2020.126541",

language = "English",

volume = "384",

pages = "1--8",

journal = "Physics Letters, Section A: General, Atomic and Solid State Physics",

issn = "0375-9601",

publisher = "Elsevier BV",

number = "22",

}

TY - JOUR

T1 - Computational universality of fungal sandpile automata

AU - Goles, Eric

AU - Tsompanas, Michail Antisthenis

AU - Adamatzky, Andrew

AU - Tegelaar, Martin

AU - Wosten, Han A.B.

AU - Martínez, Genaro J.

PY - 2020/8/6

Y1 - 2020/8/6

N2 - 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.

AB - 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.

KW - Computational universality

KW - Fungi

KW - Sandpile automata

UR - https://www.scopus.com/pages/publications/85084482875

U2 - 10.1016/j.physleta.2020.126541

DO - 10.1016/j.physleta.2020.126541

M3 - Article

AN - SCOPUS:85084482875

SN - 0375-9601

VL - 384

SP - 1

EP - 8

JO - Physics Letters, Section A: General, Atomic and Solid State Physics

JF - Physics Letters, Section A: General, Atomic and Solid State Physics

IS - 22

M1 - 126541

ER -

Computational universality of fungal sandpile automata

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this