Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

Simple Intrinsic Simulation of Cellular Automata in Oritatami Molecular Folding Model

Abstract : The Oritatami model was introduced by Geary et al (2016) to study the computational potential of RNA cotranscriptional folding as first shown in wet-lab experiments by Geary et al (Science 2014). In Oritatami model, a molecule grows component by component (named beads) into the triangular grid and folds as it grows. More precisely, the δ last nascent beads are free to move and adopt the positions that maximizes the number of bonds with the current folded structure. Geary et al (2018) proved that the Oritatami model is capable of efficient Turing universal computation using a complicated construction that simulates Turing machines via tag systems. We propose here a simple Oritatami system which intrinsically simulates arbitrary 1D cellular automata. Being intrinsic, our simulation emulates the behavior of cellular automata in a readable way and in time linear in space and time of the simulated automaton. Oritatami model has proven to be a fruitful framework to study molecular reconfigurability. Our construction relies on the development of new mecanisms which are simple enough that we believe that some simplification of them may be implemented in the wet lab. An implementation of our construction can be downloaded for testing.
Liste complète des métadonnées
Contributeur : Nicolas Schabanel <>
Soumis le : samedi 14 décembre 2019 - 08:38:40
Dernière modification le : lundi 21 décembre 2020 - 15:27:39


Fichiers produits par l'(les) auteur(s)



Daria Pchelina, Nicolas Schabanel, Shinnosuke Seki, Yuki Ubukata. Simple Intrinsic Simulation of Cellular Automata in Oritatami Molecular Folding Model. 14th LATIN 2020: São Paulo, Brazil, Jan 2021, Sao Paulo, Brazil. pp.425-436, ⟨10.1007/978-3-030-61792-9_34⟩. ⟨hal-02410874⟩



Consultations de la notice


Téléchargements de fichiers