J 2021

Self-healing turing-universal computation in morphogenetic systems

SOSÍK, Petr; Max GARZON a Jan DRASTIK

Základní údaje

Originální název

Self-healing turing-universal computation in morphogenetic systems

Autoři

SOSÍK, Petr; Max GARZON a Jan DRASTIK

Vydání

Natural Computing, Springer Science and Business Media, 2021, 1567-7818

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Nizozemské království

Utajení

není předmětem státního či obchodního tajemství

Impakt faktor

Impact factor: 1.504

Označené pro přenos do RIV

Ano

Kód RIV

RIV/47813059:19240/21:A0000880

Organizační jednotka

Filozoficko-přírodovědecká fakulta v Opavě

EID Scopus

Klíčová slova anglicky

Morphogenetic systems; Membrane computing; Self-assembly; Self-healing; Turing universality; P systems

Štítky

Příznaky

Mezinárodní význam, Recenzováno

Návaznosti

LQ1602, projekt VaV.
Změněno: 12. 1. 2023 18:15, Mgr. Kamil Matula, Ph.D.

Anotace

V originále

A morphogenetic system (M system) is an abstract computational model inspired by characteristic properties of morphogenetic phenomena such as controlled growth, self-reproduction, homeostasis and self-healing in living systems. Besides selected principles of membrane computing, M systems also rely on algorithmic self-assembly of abstract tiles unfolding in a 3D (or generally, dD) space. Explicit spatial arrangements for interaction among an M system’s components are crucial for its function. From a computational viewpoint, key features of M systems include their computational universality and their efficiency to solve difficult problems. Both computational universality (in the Turing sense) and self-healing properties (in the sense of the algorithmic tile assembly model) have been demonstrated for different M systems in prior publications. Here, we demonstrate that both of these properties can be simultaneously achieved in a single M system. We present a Turing universal string acceptor M system that also exhibits self-healing capabilities of degree 1. This result is rather surprising since Turing machines are usually very sensitive to minor damage to their internal structure. The result thus sheds light on the power and importance of geometric and spatial arrangements for the reliability and robustness of a computational system.

Přiložené soubory

Sosik-Garzon-Drastik_Self-healing-turing-uiversal-computation.pdf
Požádat o autorskou verzi souboru