Abstract
The theme of this paper is computation in Winfree’s Abstract Tile Assembly Model (TAM). We first review a simple, well-known tile assembly system (the “wedge construction”) that is capable of universal computation. We then extend the wedge construction to prove the following result: if a set of natural numbers is decidable, then it and its complement’s canonical two-dimensional representation self-assemble. This leads to a novel characterization of decidable sets of natural numbers in terms of self-assembly. Finally, we prove that our construction is, in some “natural” sense, optimal with respect to the amount of space it uses.
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
Cheng, Q., Goel, A., de Espanés, P.M.: Optimal self-assembly of counters at temperature two. In: Proceedings of the First Conference on Foundations of Nanoscience: Self-assembled Architectures and Devices (2004)
Lathrop, J.I., Lutz, J.H., Patitz, M.J., Summers, S.M.: Computability and complexity in self-assembly. In: Proceedings of The Fourth Conference on Computability in Europe, Athens, Greece, June 15-20 (to appear, 2008)
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)
Rothemund, P.W.K.: 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)
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, Brooklyn, NY, 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
Patitz, M.J., Summers, S.M. (2008). Self-assembly of Decidable Sets. In: Calude, C.S., Costa, J.F., Freund, R., Oswald, M., Rozenberg, G. (eds) Unconventional Computing. UC 2008. Lecture Notes in Computer Science, vol 5204. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-85194-3_17
Download citation
DOI: https://doi.org/10.1007/978-3-540-85194-3_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-85193-6
Online ISBN: 978-3-540-85194-3
eBook Packages: Computer ScienceComputer Science (R0)