Link: arxiv.org 2002.04012

Theorists prefer it when their models of computation are as simple as possible, without superfluous bells and whistles. In the cooperative abstract Tile Assembly Model of self-assembly, square tiles attach to each other using multi-sided cooperation of one, two or more sides. This precise control of tile binding can be directly exploited for algorithmic tasks including simulation of Turing machines and efficient (few tile types) assembly of shapes. But are cooperative bindings required for these computational tasks? The simpler-looking noncooperative (or Temperature 1) model has poor control: tiles stick if they bind on at least one side. After trying a few examples by hand one gets the sense that such poor control actually leads to poor results: long "pumped" paths that repeat the same few tiles over and over, forever. Not good for precisely and efficiently building finite structures.

Our paper proves that intuition. We show that in the noncooperative, or temperature 1, model of self-assembly, long paths of tiles are either have a segment that can be repeated forever ("pumpable") or can be blocked by other paths. The paper gives a precise sense in which efficiently and precisely building large structures is impossible in the noncooperative model -- any attempt to do so leads to either runaway growth or else prematurely blocked growth. The model definition is a bit too simple.

Accepted to STOC 2020.