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

×

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

×

N

square in the rgTAM is

O

(log

N

). In our second result, we prove that the rgTAM is Turing universal.