Difference between revisions of "Limitations of Self-Assembly at Temperature 1"
m |
|||
| (2 intermediate revisions by 2 users not shown) | |||
| 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 | ||
| − | |file=[http://self-assembly.net/mpatitz/papers/T1.pdf version in Theoretical Computer Science | + | |date=2009/03/10 |
| + | |file=[http://self-assembly.net/mpatitz/papers/T1.pdf Limitations of Self-Assembly at Temperature 1.pdf] (version in Theoretical Computer Science) | ||
}} | }} | ||
Latest revision as of 12:14, 22 June 2021
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
File
Limitations of Self-Assembly at Temperature 1.pdf (version in Theoretical Computer Science)
