表面化學反應網路的模擬能力

Abstract

化學反應網路(CRN)是一個被廣泛研究的模型，描述混合溶液中分子的相互作用。2014年，Qian和 Winfree提出了表面化學反應網路模型(sCRN)，將分子置於平面圖的節點上，達到利用空間限制分子間相互作用的效果。在此模型裡，任何分子僅能與相鄰的分子進行反應。許多後續的研究著重在sCRN的計算能力並探討分子所能長成的圖案。 為了刻畫sCRN所能完成的事情，我們將此模型與其他已被廣泛研究的分子及自我組合系統做了連結。我們證明只要給定相同的初始條件，sCRN、親合力增強磁磚自動機、細胞自動機，及阿米巴機器人都可以互相模擬(經過一些必要的旋轉和翻轉)。此外，我們也考慮了凍結系統之間的模擬，在凍結限制下任意節點的狀態都只能依照某種篇序成長。特別地，我們引入凍結sCRN，並證明了凍結親合力增強磁磚自動機及凍結細胞自動機可以被凍結sCRN模擬(經過必要的旋 轉和翻轉)。其中一個我們使用的技巧是即時著色，透過即時著色我們能賦予分子對於方向的共識。

The Chemical Reaction Network (CRN) is a well-studied model that describes the interaction of molecules in well-mixed solutions. In 2014, Qian and Winfree proposed the abstract surface chemical reaction network model (sCRN), which takes advantage of spatial separation by placing molecules on a structured surface, limiting the interaction between molecules. In this model, molecules can only react with their immediate neighbors. Many follow-up works study the computational and pattern-construction power of sCRNs.

In this work, our goal is to describe the power of sCRN by relating the model to other well-studied models in distributed computation. We show that given the same initial configuration, sCRN, affinity-strengthening tile automata, cellular automata, and amoebot can all simulate each other (up to unavoidable rotation and reflection of the pattern). As an extension, we also consider the simulation between freezing systems where the state in any fixed position can only increase according to some partial order. In particular, we introduce freezing sCRN and show that freezing affinity-strengthening tile automata and the freezing cellular automata can be simulated by freezing sCRN (up to unavoidable rotation and reflection of the pattern). One of our techniques is coloring on-the-fly, which allows all molecules in sCRN to have a global orientation.