The non-cooperative tile assembly model is not intrinsically universal or capable of bounded Turing machine simulation
The non-cooperative tile assembly model is not intrinsically universal or capable of bounded Turing machine simulation
复制标题
DOI：
10.1145/3055399.3055446
复制
发表时间：
2017-02
期刊：
影响因子：
--
通讯作者：
Pierre-Etienne Meunier;D. Woods
中科院分区：
文献类型：
--
作者：
Pierre-Etienne Meunier;D. Woods
算法自组装的领域与纳米级自组装分子系统的计算和表达能力有关。在研究良好的合作社或温度2，抽象瓷砖组装模型中，众所周知，有一个瓷砖集来模拟任何图灵机和一个本质上通用的瓷砖集，该集合模拟了模型的任何实例的形状和动力学，直到空间恢复。关于看似简单的非合作或温度1模型是否能够具有这种行为的方式，这是一个空旷的问题。在这里，我们表明，不是通过证明非合作模型中没有瓷砖设置的本质上是通用的，也不是一个能够在平面界面区域内进行时间绑定的图灵机仿真的瓷砖。尽管非合作模型从直觉上看来缺乏合作模型的复杂性和力量，但很难证明这一点。原因之一是，很少有工具可以分析平面中复杂路径的结构。本文提供了许多此类工具。第二个原因是，几乎每个明显且小的概括模型（例如，允许误差，3D，非方块瓷砖，瓷砖上的信号/电线，彼此排斥的瓷砖，平行同步增长）都赋予其良好的计算，有时甚至是模拟，力量。我们的主要结果表明，所有这些概括都可以提高计算和/或模拟能力。我们的结果适用于确定性和非确定性非合作系统。我们的第一个主要结果与以下事实形成鲜明对比：对于合作瓷砖组装模型和3D非合作瓷砖组装，都有各自的本质上是通用的瓷砖集。我们的第二个主要结果提供了一种新技术（减少模拟），以证明瓷砖组装中计算的负面结果。
The field of algorithmic self-assembly is concerned with the computational and expressive power of nanoscale self-assembling molecular systems. In the well-studied cooperative, or temperature 2, abstract tile assembly model it is known that there is a tile set to simulate any Turing machine and an intrinsically universal tile set that simulates the shapes and dynamics of any instance of the model, up to spatial rescaling. It has been an open question as to whether the seemingly simpler noncooperative, or temperature 1, model is capable of such behaviour. Here we show that this is not the case by showing that there is no tile set in the noncooperative model that is intrinsically universal, nor one capable of time-bounded Turing machine simulation within a bounded region of the plane. Although the noncooperative model intuitively seems to lack the complexity and power of the cooperative model it has been exceedingly hard to prove this. One reason is that there have been few tools to analyse the structure of complicated paths in the plane. This paper provides a number of such tools. A second reason is that almost every obvious and small generalisation to the model (e.g. allowing error, 3D, non-square tiles, signals/wires on tiles, tiles that repel each other, parallel synchronous growth) endows it with great computational, and sometimes simulation, power. Our main results show that all of these generalisations provably increase computational and/or simulation power. Our results hold for both deterministic and nondeterministic noncooperative systems. Our first main result stands in stark contrast with the fact that for both the cooperative tile assembly model, and for 3D noncooperative tile assembly, there are respective intrinsically universal tilesets. Our second main result gives a new technique (reduction to simulation) for proving negative results about computation in tile assembly.