Doubles and negatives are positive (in self-assembly)
Doubles and negatives are positive (in self-assembly)
复制标题
双打和负数都是正数（在自组装中）
作者：
Jacob Hendricks;Matthew J. Patitz;T. Rogers
在抽象图块组装模型 (aTAM) 中，当将新图块附加到不断增长的组件需要它绑定到组件中已有的多个图块时，就会发生合作现象。通常被称为“温度 2”的系统，众所周知，那些采用协作的系统非常强大（即它们在计算上是通用的，并且可以构建各种各样的形状和结构）。相反，不强制执行协作行为的 aTAM 系统（又名“温度 1”系统）被认为相对非常弱，可能无法执行复杂的计算或通过算法指导自组装过程。尽管如此，基于对 aTAM 的轻微修改的各种模型已经被开发出来，其中温度 1 系统实际上能够通过有限的合作概念进行图灵通用计算。尽管具有这种能力，但其中一些模型之前已被证明无法执行或模拟温度 2 aTAM 系统所表现出的更强的合作形式。在本文中，我们首先证明了温度 1 系统在计算上通用的另一个模型，即允许瓦片具有表现出排斥力的边缘的限制胶 TAM (rgTAM)，也无法模拟温度 2 aTAM 的强协作行为。然后，我们证明，通过将双拼块组装模型 (DTAM) 和 rgTAM 这两个模型的属性组合到 DrgTAM 中，我们得出了一个模型，该模型在温度 1 时实际上比 aTAM 在温度 2 时更强大。具体来说，温度为1的DrgTAM可以模拟任何温度的任何aTAM系统，并且它还包含aTAM中任何系统都无法模拟的系统。
In the abstract Tile Assembly Model (aTAM), the phenomenon of cooperation occurs when the attachment of a new tile to a growing assembly requires it to bind to more than one tile already in the assembly. Often referred to as “temperature-2” systems, those which employ cooperation are known to be quite powerful (i.e. they are computationally universal and can build an enormous variety of shapes and structures). Conversely, aTAM systems which do not enforce cooperative behavior, a.k.a. “temperature-1” systems, are conjectured to be relatively very weak, likely to be unable to perform complex computations or algorithmically direct the process of self-assembly. Nonetheless, a variety of models based on slight modifications to the aTAM have been developed in which temperature-1 systems are in fact capable of Turing universal computation through a restricted notion of cooperation. Despite that power, though, several of those models have previously been proven to be unable to perform or simulate the stronger form of cooperation exhibited by temperature-2 aTAM systems. In this paper, we first prove that another model in which temperature-1 systems are computationally universal, namely the restricted glue TAM (rgTAM) in which tiles are allowed to have edges which exhibit repulsive forces, is also unable to simulate the strongly cooperative behavior of the temperature-2 aTAM. We then show that by combining the properties of two such models, the Dupled Tile Assembly Model (DTAM) and the rgTAM into the DrgTAM, we derive a model which is actually more powerful at temperature-1 than the aTAM at temperature-2. Specifically, the DrgTAM, at temperature-1, can simulate any aTAM system of any temperature, and it also contains systems which cannot be simulated by any system in the aTAM.