2019/10/09 by Daniel Hader, Aaron Koch, Hader, Daniel +5
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · #Cellular Automata and Applications #Computational Geometry (cs.CG) #DNA and Biological Computing #FOS: Computer and information sciences #Modular Robots and Swarm Intelligence
paper · pdf · doi:10.48550/arxiv.1910.03950
openalex publication_date 2019/10/09 · openalex created_date 2022/07/28 · openalex updated_date 2026/07/28
We present a series of results related to mathematical models of\nself-assembling tiles and the impacts that three diverse properties have on\ntheir dynamics. We expand upon a series of prior results which showed that (1)\nthe abstract Tile Assembly Model (aTAM) is intrinsically universal (IU) [FOCS\n2012], and (2) the class of directed aTAM systems is not IU [FOCS 2016]. IU for\na model (or class of systems within a model) means that there is a universal\ntile set which can be used to simulate an arbitrary system within that model\n(or class). Furthermore, the simulation must not only produce the same\nresultant structures, it must also maintain the full dynamics of the systems\nbeing simulated modulo only a scale factor. While the FOCS 2012 result showed\nthe standard, two-dimensional (2D) aTAM is IU, here we show this is also the\ncase for the 3D version. Conversely, the FOCS 2016 result showed the class of\naTAM systems which are directed (a.k.a. deterministic, or confluent) is not IU,\nimplying that nondeterminism is fundamentally required for such simulations.\nHere, however, we show that in 3D the class of directed aTAM systems is\nactually IU, i.e. there is a universal directed simulator for them. We then\nconsider the influence of more rigid notions of dimensionality. Namely, we\nintroduce the Planar aTAM, where tiles are not only restricted to binding in\nthe plane, but also to traveling in the plane, and prove that the Planar aTAM\nis not IU, and that the class of directed systems within the Planar aTAM also\nis not IU. Finally, analogous to the Planar aTAM, we introduce the Spatial\naTAM, its 3D counterpart, and prove that it is IU.\n To prove our positive results we have not only designed, but also implemented\nwhat we believe to be the first IU tile set ever implemented and simulated in\nany tile assembly model. We've made it and a simulator which can demonstrate it\nfreely available.\n