TY - JOUR

T1 - Generating boolean functions on totalistic automata networks

AU - Goles, Eric

AU - Adamatzky, Andrew

AU - Montealegre, Pedro

AU - Ríos-Wilson, Martín

N1 - Funding Information:
AA has 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 the project 1200006, FONDECYT-Chile. MRW has recieved funding from ANID via PFCHA/DOCTORADO NACIONAL/2018 21180910 and was also supported by PIA AFB 170001.
Publisher Copyright:
©2021 Old City Publishing, Inc.

PY - 2021

Y1 - 2021

N2 - We consider the problem of studying the simulation capabilities of the dynamics of arbitrary networks of finite states machines. In these models, each node of the network takes two states 0 (passive) and 1 (active). The states of the nodes are updated in parallel following a local totalistic rule, i.e., depending only on the sum of active states. Four families of totalistic rules are considered: linear or matrix defined rules (a node takes state 1 if each of its neighbours is in state 1), threshold rules (a node takes state 1 if the sum of its neighbours exceed a threshold), isolated rules (a node takes state 1 if the sum of its neighbours equals to some single number) and interval rule (a node takes state 1 if the sum of its neighbours belong to some discrete interval). We focus in studying the simulation capabilities of the dynamics of each of the latter classes. In particular, we show that totalistic automata networks governed by matrix defined rules can only implement constant functions and other matrix defined functions. In addition, we show that t by threshold rules can generate any monotone Boolean functions. Finally, we show that networks driven by isolated and the interval rules exhibit a very rich spectrum of boolean functions as they can, in fact, implement any arbitrary Boolean functions. We complement this results by studying experimentally the set of different Boolean functions generated by totalistic rules on random graphs.

AB - We consider the problem of studying the simulation capabilities of the dynamics of arbitrary networks of finite states machines. In these models, each node of the network takes two states 0 (passive) and 1 (active). The states of the nodes are updated in parallel following a local totalistic rule, i.e., depending only on the sum of active states. Four families of totalistic rules are considered: linear or matrix defined rules (a node takes state 1 if each of its neighbours is in state 1), threshold rules (a node takes state 1 if the sum of its neighbours exceed a threshold), isolated rules (a node takes state 1 if the sum of its neighbours equals to some single number) and interval rule (a node takes state 1 if the sum of its neighbours belong to some discrete interval). We focus in studying the simulation capabilities of the dynamics of each of the latter classes. In particular, we show that totalistic automata networks governed by matrix defined rules can only implement constant functions and other matrix defined functions. In addition, we show that t by threshold rules can generate any monotone Boolean functions. Finally, we show that networks driven by isolated and the interval rules exhibit a very rich spectrum of boolean functions as they can, in fact, implement any arbitrary Boolean functions. We complement this results by studying experimentally the set of different Boolean functions generated by totalistic rules on random graphs.

KW - Boolean functions

KW - Computational biology model

KW - Computational universality

KW - Non-linear dynamics

KW - Random graphs

KW - Signal interactions

KW - Totalistic automata

UR - http://www.scopus.com/inward/record.url?scp=85107410229&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:85107410229

VL - 16

SP - 343

EP - 391

JO - International Journal of Unconventional Computing

JF - International Journal of Unconventional Computing

SN - 1548-7199

IS - 4

ER -