2016/08/16 by Austin Luchsinger, Luchsinger, Austin, Robert Schweller +3
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · #Cellular Automata and Applications #Computational Geometry (cs.CG) #DNA and Biological Computing #FOS: Computer and information sciences #Modular Robots and Swarm Intelligence #cs.CG
paper · pdf · doi:10.48550/arxiv.1608.04791
arxiv created 2016/08/16 · openalex publication_date 2016/08/16 · arxiv updated 2016/08/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The algorithmic self-assembly of shapes has been considered in several models of self-assembly. For the problem of shape construction, we consider an extended version of the Two-Handed Tile Assembly Model (2HAM), which contains positive (attractive) and negative (repulsive) interactions. As a result, portions of an assembly can become unstable and detach. In this model, we utilize fuel-efficient computation to perform Turing machine simulations for the construction of the shape. In this paper, we show how an arbitrary shape can be constructed using an asymptotically optimal number of distinct tile types (based on the shape's Kolmogorov complexity). We achieve this at O(1) scale factor in this straightforward model, whereas all previous results with sublinear scale factors utilize powerful self-assembly models containing features such as staging, tile deletion, chemical reaction networks, and tile activation/deactivation. Furthermore, the computation and construction in our result only creates constant-size garbage assemblies as a byproduct of assembling the shape.