The two-handed tile assembly model is not intrinsically universal

DOI10.1007/S00453-015-9976-YzbMATH Open1336.68068arXiv1306.6710OpenAlexW1555232400MaRDI QIDQ262271FDOQ262271

Authors: Erik D. Demaine, Trent A. Rogers, Robert T. Schweller, Scott M. Summers, Damien Woods, Matthew J. Patitz 

Publication date: 29 March 2016

Published in: Algorithmica (Search for Journal in Brave)

Abstract: The well-studied Two-Handed Tile Assembly Model (2HAM) is a model of tile assembly in which pairs of large assemblies can bind, or self-assemble, together. 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 $au$, where $au$ is some fixed positive integer. We ask whether the 2HAM is intrinsically universal, in other words we ask: is there a single universal 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 $a{u}^{\prime }<au$, each temperature-$a{u}^{\prime }$ 2HAM tile system does not simulate at least one temperature-$au$ 2HAM tile system. This impossibility result proves that the 2HAM is not intrinsically universal, in stark contrast to the simpler (single-tile addition only) abstract Tile Assembly Model which is intrinsically universal ("The tile assembly model is intrinsically universal", FOCS 2012). However, on the positive side, we prove that, for every fixed temperature $augeq2$, temperature-$au$ 2HAM tile systems are indeed intrinsically universal: in other words, for each $au$ there is a single universal 2HAM tile set $U$ that, when appropriately initialized, is capable of simulating the behavior of any temperature-$au$ 2HAM tile system. As a corollary of these results 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 $au$, there is a temperature-$au$ 2HAM system that simultaneously simulates all temperature-$au$ 2HAM systems.

Full work available at URL: https://arxiv.org/abs/1306.6710

Recommendations

• The Two-Handed Tile Assembly Model Is Not Intrinsically Universal
• Intrinsic universality in self-assembly
• The Simulation Powers and Limitations of Hierarchical Self-Assembly Systems
• Two hands are better than one (up to constant factors): self-assembly in the 2HAM vs. aTAM
• The simulation powers and limitations of higher temperature hierarchical self-assembly systems

zbMATH Keywords

tile assembly model2HAMintrinsic universality

Mathematics Subject Classification ID

Cites Work

• Strict self-assembly of discrete Sierpinski triangles
• Two hands are better than one (up to constant factors): self-assembly in the 2HAM vs. aTAM
• Intrinsic universality in self-assembly
• Combinatorial optimization problems in self-assembly
• Polyomino-Safe DNA Self-assembly via Block Replacement
• One tile to rule them all: simulating any tile assembly system with a single universal tile
• Complexities for Generalized Models of Self-Assembly
• The Two-Handed Tile Assembly Model Is Not Intrinsically Universal
• Temperature 1 self-assembly: deterministic assembly in 3D and probabilistic assembly in 2D
• Intrinsic universality in tile self-assembly requires cooperation
• Parallelism and time in hierarchical self-assembly
• Staged self-assembly: nanomanufacture of arbitrary shapes with \(O(1)\) glues
• Universal Tilings
• An Almost Totally Universal Tile Set
• Intrinsic simulations between stochastic cellular automata
• Intrinsic universality and the computational power of self-assembly
• Intrinsically universal cellular automata
• Bulking I: An abstract theory of bulking
• Bulking II: Classifications of cellular automata
• Communication complexity and intrinsic universality in cellular automata
• Four states are enough!

Cited In (12)

• The non-cooperative tile assembly model is not intrinsically universal or capable of bounded Turing machine simulation
• The Two-Handed Tile Assembly Model Is Not Intrinsically Universal
• On the effects of hierarchical self-assembly for reducing program-size complexity
• Communication complexity meets cellular automata: necessary conditions for intrinsic universality
• Intrinsic universality in self-assembly
• Two hands are better than one (up to constant factors): self-assembly in the 2HAM vs. aTAM
• Intrinsic universality and the computational power of self-assembly
• The need for seed (in the abstract Tile Assembly Model)
• Self-assembly of 4-sided fractals in the two-handed tile assembly model
• Optimal staged self-assembly of linear assemblies
• The simulation powers and limitations of higher temperature hierarchical self-assembly systems
• Self-assembly of any shape with constant tile types using high temperature

This page was built for publication: The two-handed tile assembly model is not intrinsically universal

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q262271)