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.3055446zbMath1370.68095arXiv1702.00353OpenAlexW2585365870WikidataQ130953796 ScholiaQ130953796MaRDI QIDQ4977983
Damien Woods, Pierre-Étienne Meunier
Publication date: 17 August 2017
Published in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1702.00353
Related Items (10)
Self-assembly of 4-sided fractals in the two-handed tile assembly model ⋮ Improved lower and upper bounds on the tile complexity of uniquely self-assembling a thin rectangle non-cooperatively in 3D ⋮ Building squares with optimal state complexity in restricted active self-assembly ⋮ Cold dynamics in cellular automata: a tutorial ⋮ Linear Bounds on the Size of Conformations in Greedy Deterministic Oritatami ⋮ Unique assembly verification in two-handed self-assembly ⋮ The need for seed (in the abstract Tile Assembly Model) ⋮ Unnamed Item ⋮ Geometric tiles and powers and limitations of geometric hindrance in self-assembly ⋮ Self-assembly of and optimal encoding within thin rectangles at temperature-1 in 3D
This page was built for publication: The non-cooperative tile assembly model is not intrinsically universal or capable of bounded Turing machine simulation
