MURAL - Maynooth University Research Archive Library



    Intrinsic universality in tile self-assembly requires cooperation


    Meunier, Pierre-Etienne, Patitz, Matthew J., Summers, Scott M., Theyssier, Guillaume, Winslow, Andrew and Woods, Damien (2013) Intrinsic universality in tile self-assembly requires cooperation. SODA '14: Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms. pp. 752-771.

    [thumbnail of DW_Intrinsic.pdf]
    Preview
    Text
    DW_Intrinsic.pdf

    Download (796kB) | Preview

    Abstract

    We prove a negative result on the power of a model of algorithmic self-assembly for which it has been notoriously difficult to find general techniques and results. Specifically, we prove that Winfree's abstract Tile Assembly Model, when restricted to use noncooperative tile binding, is not intrinsically universal. This stands in stark contrast to the recent result that, via cooperative binding, the abstract Tile Assembly Model is indeed intrinsically universal. Noncooperative self-assembly, also known as "temperature 1", is where tiles bind to each other if they match on one or more sides, whereas cooperative binding requires binding on multiple sides. Our result shows that the change from single- to multi-sided binding qualitatively improves the kinds of dynamics and behavior that these models of nanoscale self-assembly are capable of. Our lower bound on simulation power holds in both two and three dimensions; the latter being quite surprising given that three-dimensional noncooperative tile assembly systems simulate Turing machines. On the positive side, we exhibit a three-dimensional noncooperative self-assembly tile set capable of simulating any two-dimensional noncooperative self-assembly system. Our negative result can be interpreted to mean that Turing universal algorithmic behavior in self-assembly does not imply the ability to simulate arbitrary algorithmic self-assembly processes.
    Item Type: Article
    Keywords: Intrinsic; universality; tile; self-assembly;
    Academic Unit: Faculty of Science and Engineering > Computer Science
    Faculty of Science and Engineering > Research Institutes > Hamilton Institute
    Item ID: 15715
    Identification Number: 10.1137/1.9781611973402.56
    Depositing User: Damien Woods
    Date Deposited: 22 Mar 2022 15:04
    Journal or Publication Title: SODA '14: Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms
    Publisher: ACM Digital Library
    Refereed: Yes
    Related URLs:
    URI: https://mural.maynoothuniversity.ie/id/eprint/15715
    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