The non-cooperative tile assembly model is not intrinsically universal or capable of bounded Turing machine simulation
From MaRDI portal
Publication:4977983
DOI10.1145/3055399.3055446zbMATH Open1370.68095arXiv1702.00353OpenAlexW2585365870WikidataQ130953796 ScholiaQ130953796MaRDI QIDQ4977983FDOQ4977983
Publication date: 17 August 2017
Published in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)
Abstract: The field of algorithmic self-assembly is concerned with the computational and expressive power of nanoscale self-assembling molecular systems. In the well-studied cooperative, or temperature 2, abstract tile assembly model it is known that there is a tile set to simulate any Turing machine and an intrinsically universal tile set that simulates the shapes and dynamics of any instance of the model, up to spatial rescaling. It has been an open question as to whether the seemingly simpler noncooperative, or temperature 1, model is capable of such behaviour. Here we show that this is not the case, by showing that there is no tile set in the noncooperative model that is intrinsically universal, nor one capable of time-bounded Turing machine simulation within a bounded region of the plane. Although the noncooperative model intuitively seems to lack the complexity and power of the cooperative model it was not obvious how to prove this. One reason is that there have been few tools to analyse the structure of complicated paths in the plane. This paper provides a number of such tools. A second reason is that almost every obvious and small generalisation to the model (e.g. allowing error, 3D, non-square tiles, signals/wires on tiles, tiles that repel each other, parallel synchronous growth) endows it with great computational, and sometimes simulation, power. Our main results show that all of these generalisations provably increase computational and/or simulation power. Our results hold for both deterministic and nondeterministic noncooperative systems. Our first main result stands in stark contrast with the fact that for both the cooperative tile assembly model, and for 3D noncooperative tile assembly, there are respective intrinsically universal tilesets. Our second main result gives a new technique (reduction to simulation) for proving negative results about computation in tile assembly.
Full work available at URL: https://arxiv.org/abs/1702.00353
Cited In (11)
- Geometric tiles and powers and limitations of geometric hindrance in self-assembly
- The Two-Handed Tile Assembly Model Is Not Intrinsically Universal
- Cold dynamics in cellular automata: a tutorial
- Title not available (Why is that?)
- Linear Bounds on the Size of Conformations in Greedy Deterministic Oritatami
- Unique assembly verification in two-handed self-assembly
- Building squares with optimal state complexity in restricted active 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
- Self-assembly of and optimal encoding within thin rectangles at temperature-1 in 3D
- Improved lower and upper bounds on the tile complexity of uniquely self-assembling a thin rectangle non-cooperatively in 3D
Recommendations
- Title not available (Why is that?) 👍 👎
- Title not available (Why is that?) 👍 👎
- One Tile to Rule Them All: Simulating Any Tile Assembly System with a Single Universal Tile 👍 👎
- The Two-Handed Tile Assembly Model Is Not Intrinsically Universal 👍 👎
- Solving NP-complete problems in the tile assembly model 👍 👎
- The two-handed tile assembly model is not intrinsically universal 👍 👎
- Solving satisfiability in the tile assembly model with a constant-size tileset 👍 👎
- Universal Computation with Arbitrary Polyomino Tiles in Non-Cooperative Self-Assembly 👍 👎
- Directed non-cooperative tile assembly is decidable 👍 👎
- Nondeterministic polynomial time factoring in the tile assembly model 👍 👎
This page was built for publication: The non-cooperative tile assembly model is not intrinsically universal or capable of bounded Turing machine simulation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4977983)
