CaltechAUTHORS
  A Caltech Library Service

The Two-Handed Tile Assembly Model is not Intrinsically Universal

Demaine, Erik D. and Patitz, Matthew J. and Rogers, Trent A. and Schweller, Robert T. and Summers, Scott M. and Woods, Damien (2016) The Two-Handed Tile Assembly Model is not Intrinsically Universal. Algorithmica, 74 (2). pp. 812-850. ISSN 0178-4617. https://resolver.caltech.edu/CaltechAUTHORS:20160218-140524803

[img] PDF - Submitted Version
See Usage Policy.

996Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20160218-140524803

Abstract

The Two-Handed Tile Assembly Model (2HAM) is a model of algorithmic self-assembly in which large structures, or assemblies of tiles, are grown by the binding of smaller assemblies. In order to bind, two assemblies must have matching glues that can simultaneously touch each other, and stick together with strength that is at least the temperature τ, where τ is some fixed positive integer. We ask whether the 2HAM is intrinsically universal. In other words, we ask: is there a single 2HAM tile set U which can be used to simulate any instance of the model? Our main result is a negative answer to this question. We show that for all τ′ < τ, each temperature-τ′ 2HAM tile system does not simulate at least one temperature-τ 2HAM tile system. This impossibility result proves that the 2HAM is not intrinsically universal and stands in contrast to the fact that the (single-tile addition) abstract Tile Assembly Model is intrinsically universal. On the positive side, we prove that, for every fixed temperature τ ≥ 2, temperature-τ 2HAM tile systems are indeed intrinsically universal. In other words, for each τ there is a single intrinsically universal 2HAM tile set U_τ that, when appropriately initialized, is capable of simulating the behavior of any temperature-τ 2HAM tile system. As a corollary, we find an infinite set of infinite hierarchies of 2HAM systems with strictly increasing simulation power within each hierarchy. Finally, we show that for each τ, there is a temperature-τ 2HAM system that simultaneously simulates all temperature-τ 2HAM systems.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1007/s00453-015-9976-yDOIArticle
http://link.springer.com/article/10.1007%2Fs00453-015-9976-yPublisherArticle
http://arxiv.org/abs/1306.6710arXivDiscussion Paper
http://rdcu.be/ts6JPublisherFree ReadCube access
Additional Information:© 2015 Springer Science+Business Media New York. Received: 20 August 2014; Accepted: 12 February 2015; Published online: 19 February 2015. Matthew J. Patitz’s research was supported in part by National Science Foundation Grants CCF-1117672 and CCF-1422152. Trent A. Rogers’s research was supported by the National Science Foundation Graduate Research Fellowship Program under Grant No. DGE-1450079, and National Science Foundation Grants CCF-1117672 and CCF-1422152. Robert T. Schweller’s research was supported in part by National Science Foundation Grant CCF-1117672. Damien Woods’s research was supported by National Science Foundation Grants CCF-1219274, 0832824 (The Molecular Programming Project), CCF-1219274, and CCF-1162589. This work was initiated at the 27th Bellairs Winter Workshop on Computational Geometry held on February 11–17, 2012 in Holetown, Barbados. We thank the other participants of that workshop for a fruitful and collaborative environment. We would also like to thank an anonymous reviewer for very thorough and insightful comments, helping us to improve this version of the paper.
Funders:
Funding AgencyGrant Number
NSFCCF-1117672
NSFCCF-1422152
NSF Graduate Research FellowshipDGE-1450079
NSFCCF-1219274
NSF0832824
NSFCCF-1162589
Issue or Number:2
Record Number:CaltechAUTHORS:20160218-140524803
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20160218-140524803
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:64584
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:18 Feb 2016 22:18
Last Modified:03 Oct 2019 09:39

Repository Staff Only: item control page