Published January 2, 2011
| Version public
Journal Article
Limitations of self-assembly at temperature 1
-
1.
California Institute of Technology
-
2.
The University of Texas Rio Grande Valley
-
3.
University of Wisconsin–Platteville
Abstract
We prove that if a set X ⊆ 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.
Additional Information
© 2010 Elsevier B.V. Available online 3 September 2010. This research was supported in part by National Science Foundation grants 0652569 and 0728806. We wish to thank Maria Axenovich, Matt Cook, and Jack Lutz for useful discussions. We would also like to thank Niall Murphy, Turlough Neary, Damien Woods, and Anthony Seda for inviting us to present a preliminary version of this research at the International Workshop on The Complexity of Simple Programs, University College Cork, Ireland on December 6th and 7th, 2008. Finally, we want to thank the anonymous reviewers who poured great time and effort into their reviews and helped to make this a much better paper. The research of the first author was partially supported by NSF grant CCF:0430807, by Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery Grant R2824A01 to Lila Kari, the Canada Research Chair Award in Biocomputing to Lila Kari, and by the NSF Computing Innovation Fellowship grant. The research of the third author was supported in part by NSF-IGERT Training Project in Computational Molecular Biology Grant number DGE-0504304.Additional details
Identifiers
- Eprint ID
- 22563
- Resolver ID
- CaltechAUTHORS:20110301-084205329
Funding
- NSF
- CCF-0430807
- Natural Sciences and Engineering Research Council of Canada (NSERC)
- R2824A01
- Canada Research Chairs Program
- NSF Graduate Research Fellowship
- DGE-0504304
- NSF Computing Innovation Fellowship
- NSF
- DMS-0652569
- NSF
- CCF-0728806
Dates
- Created
-
2011-03-01Created from EPrint's datestamp field
- Updated
-
2021-11-09Created from EPrint's last_modified field