Další formáty:
BibTeX
LaTeX
RIS
@article{54943, author = {Sosík, Petr and Garzon, Max and Drastik, Jan}, article_number = {4}, doi = {http://dx.doi.org/10.1007/s11047-021-09860-4}, keywords = {Morphogenetic systems; Membrane computing; Self-assembly; Self-healing; Turing universality; P systems}, language = {eng}, issn = {1567-7818}, journal = {Natural Computing}, title = {Self-healing turing-universal computation in morphogenetic systems}, url = {https://link.springer.com/content/pdf/10.1007/s11047-021-09860-4.pdf}, volume = {20}, year = {2021} }
TY - JOUR ID - 54943 AU - Sosík, Petr - Garzon, Max - Drastik, Jan PY - 2021 TI - Self-healing turing-universal computation in morphogenetic systems JF - Natural Computing VL - 20 IS - 4 SP - 739-750 EP - 739-750 PB - Springer Science and Business Media SN - 15677818 KW - Morphogenetic systems KW - Membrane computing KW - Self-assembly KW - Self-healing KW - Turing universality KW - P systems UR - https://link.springer.com/content/pdf/10.1007/s11047-021-09860-4.pdf N2 - 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. ER -
SOSÍK, Petr, Max GARZON a Jan DRASTIK. Self-healing turing-universal computation in morphogenetic systems. \textit{Natural Computing}. Springer Science and Business Media, roč.~20, č.~4, s.~739-750. ISSN~1567-7818. doi:10.1007/s11047-021-09860-4. 2021.
|