Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published January 2, 2011 | public
Journal Article

Limitations of self-assembly at temperature 1

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

Created:
August 22, 2023
Modified:
October 23, 2023