2021
Self-healing turing-universal computation in morphogenetic systems
SOSÍK, Petr; Max GARZON and Jan DRASTIKBasic information
Original name
Self-healing turing-universal computation in morphogenetic systems
Authors
SOSÍK, Petr; Max GARZON and Jan DRASTIK
Edition
Natural Computing, Springer Science and Business Media, 2021, 1567-7818
Other information
Language
English
Type of outcome
Article in a journal
Field of Study
10201 Computer sciences, information science, bioinformatics
Country of publisher
Netherlands
Confidentiality degree
is not subject to a state or trade secret
References:
Impact factor
Impact factor: 1.504
Marked to be transferred to RIV
Yes
RIV identification code
RIV/47813059:19240/21:A0000880
Organization unit
Faculty of Philosophy and Science in Opava
UT WoS
EID Scopus
Keywords in English
Morphogenetic systems; Membrane computing; Self-assembly; Self-healing; Turing universality; P systems
Tags
International impact, Reviewed
Links
LQ1602, research and development project.
Changed: 12/1/2023 18:15, Mgr. Kamil Matula, Ph.D.
Abstract
In the original language
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.