Simple Intrinsic Simulation of Cellular Automata in Oritatami Molecular Folding Model
Simple Intrinsic Simulation of Cellular Automata in Oritatami Molecular Folding Model
复制标题
Oritatami 分子折叠模型中元胞自动机的简单本征模拟
DOI：
10.1007/978-3-030-61792-9_34
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Ubukata Yuki
中科院分区：
文献类型：
--
作者：
Pchelina Daria;Schabanel Nicolas;Seki Shinnosuke;Ubukata Yuki
Oritatami模型由Geary et al.（2016）引入，以研究RNA共转录折叠的计算潜力，如Geary et al.（Science 2014）在湿实验室实验中首次显示的那样。在Oritatami模型中，一个分子一个组件（称为珠子）地生长到三角形网格中，并在生长时折叠。更确切地说，最后的新生珠粒可以自由移动，并采用最大化与当前折叠结构的键数的位置。Geary等人（2018）证明了Oritatami模型能够使用复杂的结构进行有效的图灵通用计算，该结构通过标记系统模拟图灵机。我们在这里提出了一个简单的Oritatami系统，本质上模拟任意一维细胞自动机。作为内在的，我们的模拟仿真的行为的细胞自动机在可读的方式和时间线性的空间和时间的模拟自动机。Oritatami模型已被证明是一个富有成效的框架来研究分子的可重构性。我们的建设依赖于新的机制，这是足够简单的，我们相信，他们的一些简化可以在湿实验室的发展。我们的构造的实现可以下载进行测试。
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 the Oritatami model, a molecule grows component by component (named beads) into the triangular grid and folds as it grows. More precisely, thelast nascent beads are free to move and adopt the positions that maximize 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. The Oritatami model has proven to be a fruitful framework to study molecular reconfigurability. Our construction relies on the development of new mechanisms 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.