Restricted Glue TAS

Background

Even in an overly-simplified model such as Winfree’s abstract Tile Assembly Model (aTAM) , the theoretical power of algorithmic self-assembly is formidable. Universal computation is achievable and computable shapes self-assemble as efficiently as the limits of algorithmic information theory will allow . However, these theoretical results all depend on an important system parameter, the temperature τ, which specifies the minimum amount of binding force that a tile must experience in order to permanently bind to an assembly. The temperature τ is typically set to a value of 2 because at this temperature (and above), the mechanism of “cooperation” is available, in which the correct positioning of multiple tiles is necessary before certain additional tiles can attach. However, in temperature 1 systems, where such cooperation is unenforceable, despite the fact that they have been extensively explored , it remains an unproven conjecture that self-assembly at temperature τ < 2 is incapable of universal computation. It is also widely conjectured (most notably in ), although similarly unproven, that the efficient self-assembly of such shapes even as simple as N × N squares is impossible. Given the seeming theoretical weakness of tile assembly at temperature 1, contrasted with its computational expressiveness at temperature 2, it seems natural that experimentalists would focus their efforts on the latter. However, as is often the case, what seems promising in theory is not necessarily as promising in practice. It turns out that in laboratory implementations of tile assembly systems , it has proven difficult to build true strength-2 glues in addition to being able to strictly enforce the temperature threshold (e.g. many errors that are due to “insufficient attachment” tend to occur in practice). Therefore, the characterization of self-assembly at temperature 1 is quite worth pursuing. The restricted glue tile assembly system will aid in this endeavor.

Definition

In the aTAM, we say that a tile set \(T\) is \(\emph{glue restricted}\) if (1) the absolute value of every glue strength in \(T\) is 1, (2) the glue function is \(\emph{diagonal}\), meaning that for every glue type \(g\), the interaction between \(g\) and any other glue type is of strength 0, and of magnitude 1 between two copies of \(g\), and (3) there is a single negative-strength glue type (i.e., a repulsive force equivalent in magnitude to the binding force of a strength 1 glue).