Two-Handed Assembly Model (2HAM)

The 2-Handed Assembly Model (2HAM) is a variant of the Tile Assembly Model in which an assembly does not need to begin from a specified seed and grow only one tile at a time, but instead allows for assemblies to form from the combination of any 2 existing assemblies which can attach to each other with sufficient strength and without overlapping.

Winfree’s original model, the seeded aTAM, stipulates that assembly begins from a specially-designated “seed” tile type, and all binding events consist of the attachment of a single tile to the growing assembly that contains the seed. The seed thus serves as a nucleation point from which all further growth occurs. In reality, such single-point nucleation is difficult to enforce as tiles with matching glues may attach to each other in solution, even if neither of them is connected to the seed tile. The two-handed assembly model models this sort of growth by dispensing with the idea of a seed, and simply defining an assembly to be producible if 1) it consists of a single tile (base case), or 2) it results from the stable aggregation of two producible assemblies (recursive case). Not only is the 2HAM a more realistic model, it allows us to use the geometry of partially-formed assemblies, rather than relying solely on (error-prone) glue specificity, to enforce binding rules between subassemblies.

Characteristics

A supertile (e.g., assembly) is a positioning of tiles on the integer lattice \(\mathbb{Z}^2\). Two adjacent tiles in a supertile interact if the glues on their abutting sides are equal. Each supertile induces a binding graph, a grid graph whose vertices are tiles, with an edge between two tiles if they interact. The supertile is \(\tau\) -stable if every cut of its binding graph has strength at least \(\tau\) , where the weight of an edge is the strength of the glue it represents. That is, the supertile is stable if at least energy 2 is required to separate the supertile into two parts. A tile assembly system (TAS) is a pair \(T = (T, \tau )\), where \(T\) is a finite tile set and \(\tau\) is the temperature, usually 1 or 2. Given a TAS \(T = (T, \tau )\), a supertile is producible if either it is a single tile from \(T\), or it is the \(\tau\) -stable result of translating two producible assemblies. An supertile \(\alpha\) is terminal if for every producible supertile \(\beta\), \(\alpha\) and \(\beta\) cannot be \(\tau\) -stably attached. A TAS is directed (e.g., deterministic, confluent) if it has only one terminal, producible supertile. Given a connected shape \(X \subseteq \mathbb{Z}^2\), a TAS \(T\) produces \(X\) uniquely if every producible, terminal supertile places tiles only on positions in \(X\) (appropriately translated if necessary).

References

Sarah Cannon, Erik Demaine, Martin Demaine, Sarah Eisenstat, Matthew Patitz, Robert Schweller, Scott Summers, and Andrew Winslow, Two Hands are Better Than One (up to constant factors).

David Doty, Matthew J. Patitz, Dustin Reishus, Robert T. Schweller, and Scott M. Summers, Strong Fault-Tolerance for Self-Assembly with Fuzzy Temperature, Proceedings of the 16th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010). Las Vegas, Nevada, Oct. 2010