Computing in continuous space with self-assembling polygonal tiles (extended abstract)

DOI10.1137/1.9781611974331.CH67MaRDI QIDQ4575647zbMATH OpenOpenAlexFDO

Authors Oscar Gilbert, Jacob Hendricks, Trent A. Rogers, Matthew J. Patitz

Publication date 16 July 2018

Published in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Abstract: In this paper we investigate the computational power of the polygonal tile assembly model (polygonal TAM) at temperature 1, i.e. in non-cooperative systems. The polygonal TAM is an extension of Winfree's abstract tile assembly model (aTAM) which not only allows for square tiles (as in the aTAM) but also allows for tile shapes that are polygons. Although a number of self-assembly results have shown computational universality at temperature 1, these are the first results to do so by fundamentally relying on tile placements in continuous, rather than discrete, space. With the square tiles of the aTAM, it is conjectured that the class of temperature 1 systems is not computationally universal. Here we show that the class of systems whose tiles are composed of a regular polygon P with n > 6 sides is computationally universal. On the other hand, we show that the class of systems whose tiles consist of a regular polygon P with n <= 6 cannot compute using any known techniques. In addition, we show a number of classes of systems whose tiles consist of a non-regular polygon with n >= 3 sides are computationally universal.

Recommendations

• Universal computation with arbitrary polyomino tiles in non-cooperative self-assembly
• Intrinsic universality and the computational power of self-assembly
• Exact shapes and Turing universality at temperature 1 with a single negative glue
• Triangular tile self-assembly systems
• Limitations of Self-assembly at Temperature One

Cited in

(7)

• Complexity classes for self-assembling flexible tiles
• On the effects of hierarchical self-assembly for reducing program-size complexity
• Universal computation with arbitrary polyomino tiles in non-cooperative self-assembly
• Improved lower and upper bounds on the tile complexity of uniquely self-assembling a thin rectangle non-cooperatively in 3D
• Geometric tiles and powers and limitations of geometric hindrance in self-assembly
• Building squares with optimal state complexity in restricted active self-assembly
• The need for seed (in the abstract Tile Assembly Model)

This page was built for publication: Computing in continuous space with self-assembling polygonal tiles (extended abstract)

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