The two-handed tile assembly model is not intrinsically universal

DOI10.1007/S00453-015-9976-YMaRDI QIDQ262271zbMATH OpenOpenAlexFDO

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)

Full work available at URL https://arxiv.org/abs/1306.6710, https://authors.library.caltech.edu/64584/

zbMATH Keywords

tile assembly model2HAMintrinsic universality

Mathematics Subject Classification ID

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.

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

Cites work

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

Cited in

(11)

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

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)