Resiliency to Multiple Nucleation in Temperature~1 Self-Assembly

Published on: 2016/09/04

Abstract

Abstract. We consider problems in variations of the two-handed abstract Tile Assembly Model (2HAM), a generalization of Erik Winfree’s abstract Tile Assembly Model (aTAM). In the latter, tiles attach one-ata-time to a seed-containing assembly. In the former, tiles aggregate into supertiles that then further combine to form larger supertiles; hence, constructions must be robust to the choice of seed (nucleation) tiles. We obtain three distinct results in two 2HAM variants whose aTAM siblings are well-studied. In the first variant, called the restricted glue 2HAM (rg2HAM), glue strengths are restricted to \(−1, 0,\) or \(1\). We prove this model is Turing universal, overcoming undesired growth by breaking apart undesired computation assembly via repulsive forces. In the second 2HAM variant, the 3D 2HAM (3D2HAM), tiles are (threedimensional) cubes. We prove that assembling a (roughly two-layer) \(n\) x \(n\) square in this model is possible with \(O(log2 n)\) tile types. The construction uses “cyclic, colliding” binary counters, and assembles the shape non-deterministically. Finally, we prove that there exist 3D2HAM systems that only assemble infinite aperiodic shapes.

Authors

Matthew J. Patitz, Trent A. Rogers, Robert T. Schweller, Scott M. Summers, Andrew Winslow

File

Resiliency to Multiple Nucleation in Temperature~1 Self-Assembly.pdf