Limitations of self-assembly at temperature 1

作者：Doty David; Patitz Matthew J^*; Summers Scott M

来源：Theoretical Computer Science, 2011, 412(1-2): 145-158.

DOI：10.1016/j.tcs.2010.08.023

• Tile self-assembly
• General-purpose computation
• Temperature 1
• Semilinear set

We prove that if a set X subset of Z(2) weakly self-assembles at temperature 1 in a deterministic (Winfree) tile assembly system satisfying a natural condition known as pumpability, then X is a semilinear set. This shows that only the most simple of infinite shapes and patterns can be constructed using pumpable temperature 1 tile assembly systems, and gives evidence for the thesis that temperature 2 or higher is required to carry out general-purpose computation in a deterministic two-dimensional tile assembly system. We employ this result to show that, unlike the case of temperature 2 self-assembly, no discrete self-similar fractal weakly self-assembles at temperature 1 in a pumpable tile assembly system.

• 出版日期2011-1-2