The Impacts of Dimensionality, Diffusion, and Directedness on Intrinsic Universality in the abstract Tile Assembly Model
| Autor: | Hader, Daniel, Koch, Aaron, Patitz, Matthew J., Sharp, Michael |
|---|---|
| Rok vydání: | 2019 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | We present a series of results related to mathematical models of self-assembling tiles and the impacts that three diverse properties have on their dynamics. We expand upon a series of prior results which showed that (1) the abstract Tile Assembly Model (aTAM) is intrinsically universal (IU) [FOCS 2012], and (2) the class of directed aTAM systems is not IU [FOCS 2016]. IU for a model (or class of systems within a model) means that there is a universal tile set which can be used to simulate an arbitrary system within that model (or class). Furthermore, the simulation must not only produce the same resultant structures, it must also maintain the full dynamics of the systems being simulated modulo only a scale factor. While the FOCS 2012 result showed the standard, two-dimensional (2D) aTAM is IU, here we show this is also the case for the 3D version. Conversely, the FOCS 2016 result showed the class of aTAM systems which are directed (a.k.a. deterministic, or confluent) is not IU, implying that nondeterminism is fundamentally required for such simulations. Here, however, we show that in 3D the class of directed aTAM systems is actually IU, i.e. there is a universal directed simulator for them. We then consider the influence of more rigid notions of dimensionality. Namely, we introduce the Planar aTAM, where tiles are not only restricted to binding in the plane, but also to traveling in the plane, and prove that the Planar aTAM is not IU, and that the class of directed systems within the Planar aTAM also is not IU. Finally, analogous to the Planar aTAM, we introduce the Spatial aTAM, its 3D counterpart, and prove that it is IU. To prove our positive results we have not only designed, but also implemented what we believe to be the first IU tile set ever implemented and simulated in any tile assembly model. We've made it and a simulator which can demonstrate it freely available. Comment: A shortened version of this paper was accepted to SODA 2020 |
| Databáze: | arXiv |
| Externí odkaz: |
|