Intrinsic universality in tile self-assembly requires cooperation
Abstract
We prove a negative result on the power of a model of algorithmic self-assembly for which finding general techniques and results has been notoriously difficult. Specifically, we prove that Winfree's abstract Tile Assembly Model is not intrinsically universal when restricted to use noncooperative tile binding. This stands in stark contrast to the recent result that the abstract Tile Assembly Model is indeed intrinsically universal when cooperative binding is used (FOCS 2012). Noncooperative self-assembly, also known as "temperature 1", is where all tiles bind to each other if they match on at least one side. On the other hand, cooperative self-assembly requires that some tiles bind on at least two sides. Our result shows that the change from non-cooperative to cooperative binding qualitatively improves the range of dynamics and behaviors found in these models of nanoscale self-assembly. The result holds in both two and three dimensions; the latter being quite surprising given that three-dimensional noncooperative tile assembly systems simulate Turing machines. This shows that Turing universal behavior in self-assembly does not imply the ability to simulate all algorithmic self-assembly processes. In addition to the negative result, we exhibit a three-dimensional noncooperative self-assembly tile set capable of simulating any two-dimensional noncooperative self-assembly system. This tile set implies that, in a restricted sense, non-cooperative self-assembly is intrinsically universal for itself.
Additional Information
© 2014 SIAM. Supported in part by National Science Foundation Grant CCF-1219274. Supported in part by National Science Foundation Grant CCF-1117672. Supported in part by grant 'Agence Nationale de la Recherche ANR-09-BLAN-0164'. Supported in part by National Science Foundation grants CCF-0830734 and CBET-0941538. Supported by National Science Foundation grants 0832824 (The Molecular Programming Project), CCF-1219274, and CCF-1162589.Attached Files
Published - 1_2E9781611973402_2E56.pdf
Files
Name | Size | Download all |
---|---|---|
md5:0d717ac658a4829df1a3ba2eb16d30d6
|
607.9 kB | Preview Download |
Additional details
- Eprint ID
- 72482
- Resolver ID
- CaltechAUTHORS:20161130-161823998
- CCF-1219274
- NSF
- CCF-1117672
- NSF
- ANR-09-BLAN-0164
- Agence Nationale pour la Recherche (ANR)
- CCF-0830734
- NSF
- CBET-0941538
- NSF
- CCF-0832824
- NSF
- CCF-1219274
- NSF
- CCF-1162589
- NSF
- Created
-
2016-12-01Created from EPrint's datestamp field
- Updated
-
2021-11-11Created from EPrint's last_modified field