Exact Shapes and Turing Universality at Temperature 1 with a Single Negative Glue

摘要

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 N x N 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 N × N squares) becomes unknown. On the plus side, the aTAM, at temperature 1, is not only Turing universal but also supports the efficient self-assembly N × N 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 show that the tile complexity of uniquely producing an N x N square in the rgTAM is O(logiV). In our second result, we prove that the rgTAM is Turing universal.