Difference between revisions of "Limitations of Self-Assembly at Temperature 1"
Wiki admin (talk | contribs) |
|||
Line 10: | Line 10: | ||
temperature 1 in a pumpable tile assembly system. | temperature 1 in a pumpable tile assembly system. | ||
|authors=David Doty, Matthew J. Patitz, and Scott M. Summers | |authors=David Doty, Matthew J. Patitz, and Scott M. Summers | ||
+ | |date=2009/03/10 | ||
|file=[http://self-assembly.net/mpatitz/papers/T1.pdf version in Theoretical Computer Science] | |file=[http://self-assembly.net/mpatitz/papers/T1.pdf version in Theoretical Computer Science] | ||
}} | }} |
Revision as of 15:08, 23 January 2012
Published on: 2009/03/10
Abstract
We prove that if a set \(X \subseteq \mathbb{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.
Authors
David Doty, Matthew J. Patitz, and Scott M. Summers