Generating boolean functions on totalistic automata networks

Eric Goles, Andrew Adamatzky, Pedro Montealegre, Martín Ríos-Wilson

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish
Pages (from-to)343-391
Number of pages49
JournalInternational Journal of Unconventional Computing
Volume16
Issue number4
StatePublished - 2021
Externally publishedYes

Keywords

  • Boolean functions
  • Computational biology model
  • Computational universality
  • Non-linear dynamics
  • Random graphs
  • Signal interactions
  • Totalistic automata

Fingerprint

Dive into the research topics of 'Generating boolean functions on totalistic automata networks'. Together they form a unique fingerprint.

Cite this