Abstract
This paper explores the impact of geometry on computability and complexity in Winfree’s model of nanoscale self-assembly. We work in the two-dimensional tile assembly model, i.e., in the discrete Euclidean plane ℤ ×ℤ. Our first main theorem says that there is a roughly quadratic function f such that a set A ⊆ ℤ + is computably enumerable if and only if the set X A = { (f(n), 0) | n ∈ A } – a simple representation of A as a set of points on the x-axis – self-assembles in Winfree’s sense. In contrast, our second main theorem says that there are decidable sets D ⊆ ℤ ×ℤ that do not self-assemble in Winfree’s sense.
Our first main theorem is established by an explicit translation of an arbitrary Turing machine M to a modular tile assembly system \(\mathcal{T}_M\), together with a proof that \(\mathcal{T}_M\) carries out concurrent simulations of M on all positive integer inputs.
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.: Towards a mathematical theory of self-assembly, Tech. report, University of Southern California (2000)
Bachrach, J., Beal, J.: Building spatial computers, Tech. report, MIT CSAIL (2007)
Beal, J., Sussman, G.: Biologically-inspired robust spatial programming, Tech. report, MIT (2005)
Hartmanis, J., Stearns, R.E.: On the computational complexity of algorithms. Transactions of the American Mathematical Society 117, 285–306 (1965)
Lathrop, J.I., Lutz, J.H., Summers, S.M.: Strict self-assembly of discrete Sierpinski triangles. In: Proceedings of The Third Conference on Computability in Europe, Siena, Italy, June 18-23, 2007 (2007)
Reif, J.H.: Molecular assembly and computation: From theory to experimental demonstrations. In: Proceedings of the Twenty-Ninth International Colloquium on Automata, Languages and Programming, pp. 1–21 (2002)
Paul, W.K.: Rothemund, Theory and experiments in algorithmic self-assembly, Ph.D. thesis, University of Southern California (December 2001)
Rothemund, P.W.K., Winfree, E.: The program-size complexity of self-assembled squares (extended abstract). In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pp. 459–468 (2000)
Seeman, N.C.: Nucleic-acid junctions and lattices. Journal of Theoretical Biology 99, 237–247 (1982)
Soloveichik, D., Winfree, E.: Complexity of self-assembled shapes. SIAM Journal on Computing 36, 1544–1569 (2007)
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, 1962, Polytechnic Press of Polytechnic Inst. of Brooklyn, pp. 23–55 (1963)
Winfree, E.: Algorithmic self-assembly of DNA, Ph.D. thesis, California Institute of Technology (June 1998)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lathrop, J.I., Lutz, J.H., Patitz, M.J., Summers, S.M. (2008). Computability and Complexity in Self-assembly. In: Beckmann, A., Dimitracopoulos, C., Löwe, B. (eds) Logic and Theory of Algorithms. CiE 2008. Lecture Notes in Computer Science, vol 5028. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-69407-6_38
Download citation
DOI: https://doi.org/10.1007/978-3-540-69407-6_38
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-69405-2
Online ISBN: 978-3-540-69407-6
eBook Packages: Computer ScienceComputer Science (R0)