Abstract
We prove that if a set X ⊆ ℤ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 finite union of semi-doubly periodic sets. 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 tile assembly system. Finally, we show that general-purpose computation is possible at temperature 1 if negative glue strengths are allowed in the tile assembly model.
This research was supported in part by National Science Foundation grants 0652569 and 0728806.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Adleman, L.M., Kari, J., Kari, L., Reishus, D.: On the decidability of self-assembly of infinite ribbons. In: Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, pp. 530–537 (2002)
Lathrop, J.I., Lutz, J.H., Summers, S.M.: Strict self-assembly of discrete Sierpinski triangles. Theoretical Computer Science 410, 384–405 (2009)
Patitz, M.J., Summers, S.M.: Self-assembly of decidable sets. In: Calude, C.S., Costa, J.F., Freund, R., Oswald, M., Rozenberg, G. (eds.) UC 2008. LNCS, vol. 5204, pp. 206–219. Springer, Heidelberg (2008)
Rothemund, P.W.K.: Theory and experiments in algorithmic self-assembly. Ph.D. thesis, University of Southern California (December 2001)
Rothemund, P.W.K., Papadakis, N., Winfree, E.: Algorithmic self-assembly of dna sierpinski triangles. PLoS Biology 2(12) (2004)
Seeman, N.C.: Nucleic-acid junctions and lattices. Journal of Theoretical Biology 99, 237–247 (1982)
Wang, H.: Proving theorems by pattern recognition – II. The Bell System Technical Journal XL(1), 1–41 (1961)
Wang, H.: Dominoes and the AEA case of the decision problem. In: Proceedings of the Symposium on Mathematical Theory of Automata, New York, pp. 23–55. Polytechnic Press of Polytechnic Inst. of Brooklyn, Brooklyn (1962/1963)
Winfree, E.: Algorithmic self-assembly of DNA. Ph.D. thesis, California Institute of Technology (June 1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Doty, D., Patitz, M.J., Summers, S.M. (2009). Limitations of Self-assembly at Temperature One. In: Deaton, R., Suyama, A. (eds) DNA Computing and Molecular Programming. DNA 2009. Lecture Notes in Computer Science, vol 5877. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-10604-0_4
Download citation
DOI: https://doi.org/10.1007/978-3-642-10604-0_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-10603-3
Online ISBN: 978-3-642-10604-0
eBook Packages: Computer ScienceComputer Science (R0)