2022
Computational Universality and Efficiency in Morphogenetic Systems
SOSÍK, Petr a Jan DRASTIKZákladní údaje
Originální název
Computational Universality and Efficiency in Morphogenetic Systems
Autoři
SOSÍK, Petr a Jan DRASTIK
Vydání
13419. vyd. Cham, Machines, Computations, and Universality, od s. 158-171, 14 s. 2022
Nakladatel
Springer Science and Business Media Deutschland GmbH
Další údaje
Jazyk
angličtina
Typ výsledku
Stať ve sborníku
Obor
10201 Computer sciences, information science, bioinformatics
Stát vydavatele
Německo
Utajení
není předmětem státního či obchodního tajemství
Forma vydání
elektronická verze "online"
Odkazy
Impakt faktor
Impact factor: 0.402 v roce 2005
Označené pro přenos do RIV
Ano
Kód RIV
RIV/47813059:19240/22:A0000999
Organizační jednotka
Filozoficko-přírodovědecká fakulta v Opavě
ISBN
978-3-031-13501-9
ISSN
UT WoS
EID Scopus
Klíčová slova anglicky
Membrane computing; Morphogenetic system; P versus NP; Self-assembly; Universal computation
Příznaky
Mezinárodní význam, Recenzováno
Změněno: 2. 1. 2023 10:38, Mgr. Kamil Matula, Ph.D.
Anotace
V originále
The topic of computational universality and efficiency of various types of abstract machines is still subject of intensive research. Besides many crucial open theoretical problems, there are also numerous potential applications, e.g., in construction of small physical computing machines (nano-automata), harnessing algorithmic processes in biology or biochemistry, efficient solving of computationally hard problems and many more. The study of computability and complexity of new abstract models can help to understand the borderline between non-universality and universality, or between tractable and intractable problems. Here we study computational universality (in Turing sense) and computational complexity in the framework of morphogenetic (M) systems—computational models combining properties of membrane systems and algorithmic self-assembly of pre-defined atomic polytopes. Even very simple morphogenetic systems can exhibit complex self-organizing behaviour and phenomena such as controlled growth, self-reproduction, homeostasis and self-healing. We present two small universal M systems, one of which is additionally self-healing. Then we show how the borderline P versus NP can be characterized by some properties of morphogenetic systems.