MURAL - Maynooth University Research Archive Library



    The two-handed tile assembly model is not intrinsically universal


    Demaine, Erik D., Patitz, Mathhew J., Rogers, Trent A., Schweller, Robert, Summers, Scott M. and Woods, Damien (2016) The two-handed tile assembly model is not intrinsically universal. Algorithmica, 74 (2). pp. 812-850. ISSN 1432-0541

    [thumbnail of Woods_Two-Handed_2016.pdf]
    Preview
    Text
    Woods_Two-Handed_2016.pdf

    Download (1MB) | Preview

    Abstract

    The Two-Handed Tile Assembly Model (2HAM) is a model of algorithmic self-assembly in which large structures, or assemblies of tiles, are grown by the binding of smaller assemblies. In order to bind, two assemblies must have matching glues that can simultaneously touch each other, and stick together with strength that is at least the temperature τ, where τ is some fixed positive integer. We ask whether the 2HAM is intrinsically universal. In other words, we ask: is there a single 2HAM tile set U which can be used to simulate any instance of the model? Our main result is a negative answer to this question. We show that for all τ′<τ, each temperature-τ′ 2HAM tile system does not simulate at least one temperature-τ 2HAM tile system. This impossibility result proves that the 2HAM is not intrinsically universal and stands in contrast to the fact that the (single-tile addition) abstract Tile Assembly Model is intrinsically universal. On the positive side, we prove that, for every fixed temperature τ≥2, temperature-τ 2HAM tile systems are indeed intrinsically universal. In other words, for each τ there is a single intrinsically universal 2HAM tile set Uτ that, when appropriately initialized, is capable of simulating the behavior of any temperature-τ 2HAM tile system. As a corollary, we find an infinite set of infinite hierarchies of 2HAM systems with strictly increasing simulation power within each hierarchy. Finally, we show that for each τ, there is a temperature-τ 2HAM system that simultaneously simulates all temperature-τ 2HAM systems.
    Item Type: Article
    Keywords: Tile-assembly; Intrinsic universality; 2HAM; Tile assembly model;
    Academic Unit: Faculty of Science and Engineering > Computer Science
    Faculty of Science and Engineering > Research Institutes > Hamilton Institute
    Item ID: 12404
    Identification Number: 10.1007/s00453-015-9976-y
    Depositing User: Damien Woods
    Date Deposited: 10 Feb 2020 18:06
    Journal or Publication Title: Algorithmica
    Publisher: Springer
    Refereed: Yes
    Related URLs:
    URI: https://mu.eprints-hosting.org/id/eprint/12404
    Use Licence: This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

    Repository Staff Only (login required)

    Item control page
    Item control page

    Downloads

    Downloads per month over past year

    Origin of downloads