The simulation powers and limitations of higher temperature hierarchical self-assembly systems
From MaRDI portal
Publication:4601151
DOI10.3233/FI-2017-1579zbMATH Open1378.68040arXiv1503.04502MaRDI QIDQ4601151FDOQ4601151
Trent A. Rogers, Matthew J. Patitz, Jacob Hendricks
Publication date: 19 January 2018
Published in: Fundamenta Informaticae (Search for Journal in Brave)
Abstract: In this paper, we extend existing results about simulation and intrinsic universality in a model of tile-based self-assembly. Namely, we work within the 2-Handed Assembly Model (2HAM), which is a model of self-assembly in which assemblies are formed by square tiles that are allowed to combine, using glues along their edges, individually or as pairs of arbitrarily large assemblies in a hierarchical manner, and we explore the abilities of these systems to simulate each other when the simulating systems have a higher "temperature" parameter, which is a system wide threshold dictating how many glue bonds must be formed between two assemblies to allow them to combine. It has previously been shown that systems with lower temperatures cannot simulate arbitrary systems with higher temperatures, and also that systems at some higher temperatures can simulate those at particular lower temperatures, creating an infinite set of infinite hierarchies of 2HAM systems with strictly increasing simulation power within each hierarchy. These previous results relied on two different definitions of simulation, one (strong simulation) seemingly more restrictive than the other (standard simulation), but which have previously not been proven to be distinct. Here we prove distinctions between them by first fully characterizing the set of pairs of temperatures such that the high temperature systems are intrinsically universal for the lower temperature systems (i.e. one tile set at the higher temperature can simulate any at the lower) using strong simulation. This includes the first impossibility result for simulation downward in temperature. We then show that lower temperature systems which cannot be simulated by higher temperature systems using the strong definition, can in fact be simulated using the standard definition, proving the distinction between the types of simulation.
Full work available at URL: https://arxiv.org/abs/1503.04502
Recommendations
- The Simulation Powers and Limitations of Hierarchical Self-Assembly Systems
- The Two-Handed Tile Assembly Model Is Not Intrinsically Universal
- The two-handed tile assembly model is not intrinsically universal
- Intrinsic universality in self-assembly
- Complexities for high-temperature two-handed tile self-assembly
Cited In (6)
- Limitations of self-assembly at temperature 1
- Limitations of Self-assembly at Temperature One
- On the effects of hierarchical self-assembly for reducing program-size complexity
- The Simulation Powers and Limitations of Hierarchical Self-Assembly Systems
- Resiliency to multiple nucleation in temperature-1 self-assembly
- Self-assembly of 4-sided fractals in the two-handed tile assembly model
This page was built for publication: The simulation powers and limitations of higher temperature hierarchical self-assembly systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4601151)
