Meunier, Pierre-Étienne, Regnault, Damien and Woods, Damien (2020) The program-size complexity of self-assembled paths. STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. pp. 727-737.
Preview
DW_the program-size.pdf
Download (344kB) | Preview
Abstract
We prove a Pumping Lemma for the noncooperative abstract Tile Assembly Model, a model central to the theory of algorithmic self-assembly since the beginning of the field. This theory suggests, and our result proves, that small differences in the nature of adhesive bindings between abstract square molecules gives rise to vastly different expressive capabilities. In the cooperative abstract Tile Assembly Model, square tiles attach to each other using multi-sided cooperation of one, two or more sides. This precise control of tile binding is directly exploited for algorithmic tasks including growth of specified shapes using very few tile types, as well as simulation of Turing machines and even self-simulation of self-assembly systems. But are cooperative bindings required for these computational tasks? The definitionally simpler noncooperative (or Temperature 1) model has poor control over local binding events: tiles stick if they bind on at least one side. This has led to the conjecture that it is impossible for it to exhibit precisely controlled growth of computationally-defined shapes. Here, we prove such an impossibility result. We show that any planar noncooperative system that attempts to grow large algorithmically-controlled tile-efficient assemblies must also grow infinite non-algorithmic (pumped) structures with a simple closed-form description, or else suffer blocking of intended algorithmic structures. Our result holds for both directed and nondirected systems, and gives an explicit upper bound of (8|T|)4|T|+1(5|σ| + 6), where |T| is the size of the tileset and |σ| is the size of the seed assembly, beyond which any path of tiles is pumpable or blockable.
Item Type: | Article |
---|---|
Keywords: | Self-assembly; tilings; pumping lemma; DNA computing; |
Academic Unit: | Assisting Living & Learning,ALL institute Faculty of Science and Engineering > Electronic Engineering Faculty of Science and Engineering > Research Institutes > Hamilton Institute |
Item ID: | 15712 |
Identification Number: | 10.1145/3357713.3384263 |
Depositing User: | Damien Woods |
Date Deposited: | 22 Mar 2022 14:31 |
Journal or Publication Title: | STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing |
Publisher: | ACM Digital Library |
Refereed: | Yes |
Related URLs: | |
URI: | https://mu.eprints-hosting.org/id/eprint/15712 |
Use Licence: | This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here |
Repository Staff Only (login required)
Downloads
Downloads per month over past year