Doubles and negatives are positive (in self-assembly)
From MaRDI portal
Publication:2003447
DOI10.1007/978-3-319-08123-6_16zbMATH Open1415.68086arXiv1403.3841OpenAlexW1841366214MaRDI QIDQ2003447FDOQ2003447
Trent A. Rogers, Matthew J. Patitz, Jacob Hendricks
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
- Doubles and negatives are positive (in self-assembly)
- 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
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Other nonclassical models of computation (68Q09)
Cites Work
- Negative interactions in irreversible self-assembly
- 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
- Title not available (Why is that?)
- 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
- Doubles and negatives are positive (in self-assembly)
- Signal transmission across tile assemblies: 3D static tiles simulate active self-assembly by 2D signal-passing tiles
- The Power of Duples (in Self-Assembly): It’s Not So Hip to Be Square
Cited In (3)
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)
