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.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
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)