The Impacts of Dimensionality, Diffusion, and Directedness on Intrinsic\n Universality in the abstract Tile Assembly Model Article Swipe

MAKE IMPACT

Daniel Hader , Aaron Koch , Matthew J. Patitz , M. Keith Sharp · YOU? · · 2019 · Open Access · · DOI: https://doi.org/10.48550/arxiv.1910.03950

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

Type

preprint

Landing Page

http://arxiv.org/abs/1910.03950

PDF

https://arxiv.org/pdf/1910.03950

OA Status

green

Cited By

1

Related Works

10

OpenAlex ID

https://openalex.org/W4288093921

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W4288093921

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.1910.03950

Digital Object Identifier

Title

The Impacts of Dimensionality, Diffusion, and Directedness on Intrinsic\n Universality in the abstract Tile Assembly Model

Work title

Type

preprint

OpenAlex work type

Publication year

2019

Year of publication

Publication date

2019-10-09

Full publication date if available

Authors

Daniel Hader, Aaron Koch, Matthew J. Patitz, M. Keith Sharp

List of authors in order

Landing page

https://arxiv.org/abs/1910.03950

Publisher landing page

PDF URL

https://arxiv.org/pdf/1910.03950

Direct link to full text PDF

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/1910.03950

Direct OA link when available

Concepts

Tile, Modulo, Curse of dimensionality, Universality (dynamical systems), Planar, Class (philosophy), Computer science, Mathematics, Discrete mathematics, Physics, Artificial intelligence, Quantum mechanics, Computer graphics (images), Art, Visual arts

Top concepts (fields/topics) attached by OpenAlex

Cited by

1

Total citation count in OpenAlex

Citations by year (recent)

2023: 1

Per-year citation counts (last 5 years)

Related works (count)

10

Other works algorithmically related by OpenAlex

Full payload