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 \(\tau\), which specifies the minimum amount of binding force that a tile must experience in order to permanently bind to an assembly. The temperature \(\tau\) 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 \(\tau < 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 \times 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).

Results with the rgTAS

First, we first show that the tile complexity of uniquely producing an \(N \times N\) square with an rgTAS is O(\(\dfrac{log n}{log log n}\)), matching the upper and lower bounds for the aTAM in general. In another result, we prove that the rgTAS class is Turing universal in the aTAM by exhibiting a construction which simulates an arbitrary Turing machine.

Partially Restricted Glue TAS

Due to the potential difficulty of experimentally implementing negative strength glues such that the magnitude of their strengths is very nearly exactly equivalent to that of the positive strength-1 glues, we also introduce another type of tile assembly system, which we refer to as partially restricted glue tile assembly system, or prgTAS. A tile set in a prgTAS has the same properties as those for rgTASs, except for the fact that the magnitude of the strength of the single negative glue is guaranteed to be at least 1, but may in fact be greater (i.e. the effective glue strength could actually be −2, −3, etc.).

Results with the prgTAS

Results for the prgTAS consist of a construction with O(log n) tile complexity for building N × N squares, and a construction which simulates a Turing machine but with a greater scaling factor than for the rgTAS construction.