Computer Science – Emerging Technologies
Scientific paper
2011-05-06
Computer Science
Emerging Technologies
Original version appeared in DNA Computing 17. This is an updated, journal version with a pair of new results and several othe
Scientific paper
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 \times 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 \times N$ squares) becomes unknown. On the plus side, the aTAM, at temperature 1, isn't only Turing universal but also supports the efficient self-assembly $N \times N$ squares if self-assembly is allowed to utilize three spatial dimensions (Fu, Schweller and Cook, SODA 2011). We investigate the theoretical "power" of a seemingly simple, restrictive class of tile assembly systems (TASs) in which (1) the absolute value of every glue strength is 1, (2) there's a single negative strength glue type and (3) unequal glues can't interact. We call these the \emph{restricted glue} TASs (rgTAS). We first show the tile complexity of producing an $N \times N$ square with an rgTAS is $O(\frac{\log n}{\log \log n})$. We also prove that rgTASs are Turing universal with a construction that simulates an arbitrary Turing machine. Next, we provide results for a variation of the rgTAS class, partially restricted glue TASs, which is similar except that the magnitude of the negative glue's strength can only assumed to be $\ge 1$. These results consist of a construction with $O(\log n)$ tile complexity for building $N \times N$ squares, and one which simulates a Turing machine but with a greater scaling factor than for the rgTAS construction.
Patitz Matthew J.
Schweller Robert T.
Summers Scott M.
No associations
LandOfFree
Efficient Squares and Turing Universality at Temperature 1 with a Unique Negative Glue does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Efficient Squares and Turing Universality at Temperature 1 with a Unique Negative Glue, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient Squares and Turing Universality at Temperature 1 with a Unique Negative Glue will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-575948