Meunier, Pierre-Étienne and 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

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:	https://doi.org/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
URI:	Publisher
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)

Item control page

Downloads

Origin of downloads