Difference between revisions of "Limitations of Self-Assembly at Temperature 1"
(Created page with "{{PaperTemplate |title=Limitations of Self-Assembly at Temperature 1 |abstract=We prove that if a set $X \subseteq \mathbb{Z}^2$ weakly self-assembles at temperature 1 in a deter...") |
|||
| 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=T1.pdf | + | |file=[T1.pdf version in Theoretical Computer Science] |
}} | }} | ||
Revision as of 00:20, 4 December 2011
Published on:
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
[T1.pdf version in Theoretical Computer Science]
