Exact Shapes and Turing Universality at Temperature 1 with a Single Negative Glue
Published on:
Abstract
Is Winfree's abstract Tile Assembly Model (aTAM) "powerful?" Well, if certain tiles are required to "cooperate" in order to be able to bind to a growing tile assembly (a.k.a., temperature 2 self-assembly), then Turing universal computation and the efficient self-assembly of <m>N \times N</m> squares is achievable in the aTAM (Rotemund and Winfree, STOC 2000). So yes, in a computational sense, the aTAM is quite powerful. However, if one completely removes this cooperativity condition (a.k.a., temperature 1 self-assembly), then the computational "power" of the aTAM (i.e., its ability to support Turing universal computation and the efficient self-assembly of <m>N \times N</m> squares) becomes unknown. On the plus side, the aTAM, at temperature 1, is not only Turing universal but also supports the efficient self-assembly <m>N \times N</m> squares if self-assembly is allowed to utilize three spatial dimensions (Fu, Schweller and Cook, SODA 2011). In this paper, we investigate the theoretical "power" of a seemingly simple, restrictive variant of Winfree's aTAM in which (1) the absolute value of every glue strength is 1, (2) there is a single negative strength glue type and (3) unequal glues cannot interact (i.e., glue functions must be "diagonal"). We call this abstract model of self-assembly the restricted glue Tile Assembly Model (rgTAM). We achieve two positive results. First, we first show that the tile complexity of uniquely producing an <m>N \times N</m> square in the rgTAM is <m>O(\log N)</m>. In our second result, we prove that the rgTAM is Turing universal.
Authors
Matthew J. Patitz, Robert T. Schweller, and Scott M. Summers
