2011/05/05 by Matthew J. Patitz, Robert Schweller, Robert T. Schweller +4
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · #Cellular Automata and Applications #Computational Geometry (cs.CG) #DNA and Biological Computing #Emerging Technologies (cs.ET) #FOS: Computer and information sciences #Modular Robots and Swarm Intelligence #cs.CG #cs.ET
paper · pdf · doi:10.48550/arxiv.1105.1215
Original version appeared in DNA Computing 17. This is an updated, journal version with a pair of new results and several other changes
openalex publication_date 2011/05/05 · arxiv created 2012/02/01 · arxiv updated 2012/02/02 · openalex created_date 2022/09/14 · openalex updated_date 2026/07/28
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, isn't 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). 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 restricted glue TASs (rgTAS). We first show the tile complexity of producing an N × N square with an rgTAS is O((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 ≥ 1. These results consist of a construction with O(log n) tile complexity for building N × N squares, and one which simulates a Turing machine but with a greater scaling factor than for the rgTAS construction.