Doubles and negatives are positive (in self-assembly)

DOI10.1007/978-3-319-08123-6_16zbMATH Open1415.68086arXiv1403.3841OpenAlexW1841366214MaRDI QIDQ2003447FDOQ2003447

Authors: Jacob Hendricks, Matthew J. Patitz, Trent A. Rogers 

Publication date: 8 July 2019

Published in: Natural Computing, Unconventional Computation and Natural Computation (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1403.3841

Recommendations

• Exact shapes and Turing universality at temperature 1 with a single negative glue
• The power of duples (in self-assembly): it's not so hip to be square
• The power of duples (in self-assembly): it's not so hip to be square
• Intrinsic universality in tile self-assembly requires cooperation

zbMATH Keywords

Turing universalityintrinsic universalityself-assemblytile-assembly model

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Other nonclassical models of computation (68Q09)

Cites Work

• Exact shapes and Turing universality at temperature 1 with a single negative glue
• The program-size complexity of self-assembled squares (extended abstract)
• Asynchronous signal passing for tile self-assembly: fuel efficient computation and efficient assembly of shapes
• The Two-Handed Tile Assembly Model Is Not Intrinsically Universal
• Temperature 1 self-assembly: deterministic assembly in 3D and probabilistic assembly in 2D
• Computability and complexity in self-assembly
• Intrinsic universality in tile self-assembly requires cooperation
• Complexity of Self‐Assembled Shapes
• Self-assembly of decidable sets
• Limitations of self-assembly at temperature 1
• The power of duples (in self-assembly): it's not so hip to be square

This page was built for publication: Doubles and negatives are positive (in self-assembly)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2003447)