In the abstract Tile Assembly Model (aTAM) square tiles self-assemble, autonomously binding via glues on their edges, to form structures. Algorithmic aTAM systems can be designed in which the patterns of tile attachments are forced to follow the execution of targeted algorithms. Such systems have been proven to be computationally universal as well as intrinsically universal (IU), a notion borrowed and adapted from cellular automata showing that a single tile set exists which is capable of simulating all aTAM systems (FOCS 2012). The input to an algorithmic aTAM system can be provided in a variety of ways, with a common method being via the ``seed'' assembly, which is a pre-formed assembly from which all growth propagates. In this paper we present a series of results which investigate the the trade-offs of using seeds consisting of a single tile, versus those containing multiple tiles. We show that arbitrary systems with multi-tile seeds cannot be converted to functionally equivalent systems with single-tile seeds without using a scale factor > 1. We prove tight bounds on the scale factor required, and also present a construction which uses a large scale factor but an optimal number of unique tile types. That construction is then used to develop a construction that performs simultaneous simulation of all aTAM systems in parallel, as well as to display a connection to other tile-based self-assembly models via the notion of intrinsic universality.
翻译:抽象的 Tile 组装模型( aTAM) 平方砖块自组成形结构 。 解算 ATAM 系统可以设计出一个通用的方法, 使牌附加图案模式被迫跟随目标算法的实施。 这些系统已被证明是通用且内在通用的( IU ), 从细胞自动图中借用和修改的概念, 表明存在一个能够模拟所有 ATAM 系统( FOCS 2012) 的单一瓷砖组。 以多种方式提供对算法的 ATAM 系统的投入, 可以通过“ 种子” 组式提供一种通用的方法, 这是所有增长都来自的预成型组式组式组式。 在本文中, 我们提出了一系列结果, 调查使用由单盘构成的种子和含有多砖的种子的种子之间的交易取舍。 我们表明, 具有多盘种子的任意系统不能转换为功能等同系统, 使用单盘种子系统, 而不用比例要素 > 。 我们证明, 一个通用的方法是“ 种子” 组合组合组合组合组合组合组合组合成一个大型的模型, 使用这个模型, 这个模型的模型是用来进行最优的模型的模型。