Back to Search Start Over

Doubles and negatives are positive (in self-assembly).

Authors :
Hendricks, Jacob
Patitz, Matthew
Rogers, Trent
Source :
Natural Computing. Mar2016, Vol. 15 Issue 1, p69-85. 17p.
Publication Year :
2016

Abstract

In the abstract Tile Assembly Model (aTAM), the phenomenon of cooperation occurs when the attachment of a new tile to a growing assembly requires it to bind to more than one tile already in the assembly. Often referred to as 'temperature-2' systems, those which employ cooperation are known to be quite powerful (i.e. they are computationally universal and can build an enormous variety of shapes and structures). Conversely, aTAM systems which do not enforce cooperative behavior, a.k.a. 'temperature-1' systems, are conjectured to be relatively very weak, likely to be unable to perform complex computations or algorithmically direct the process of self-assembly. Nonetheless, a variety of models based on slight modifications to the aTAM have been developed in which temperature-1 systems are in fact capable of Turing universal computation through a restricted notion of cooperation. Despite that power, though, several of those models have previously been proven to be unable to perform or simulate the stronger form of cooperation exhibited by temperature-2 aTAM systems. In this paper, we first prove that another model in which temperature-1 systems are computationally universal, namely the restricted glue TAM (rgTAM) in which tiles are allowed to have edges which exhibit repulsive forces, is also unable to simulate the strongly cooperative behavior of the temperature-2 aTAM. We then show that by combining the properties of two such models, the Dupled Tile Assembly Model (DTAM) and the rgTAM into the DrgTAM, we derive a model which is actually more powerful at temperature-1 than the aTAM at temperature-2. Specifically, the DrgTAM, at temperature-1, can simulate any aTAM system of any temperature, and it also contains systems which cannot be simulated by any system in the aTAM. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
15677818
Volume :
15
Issue :
1
Database :
Academic Search Index
Journal :
Natural Computing
Publication Type :
Academic Journal
Accession number :
113395063
Full Text :
https://doi.org/10.1007/s11047-015-9513-6