Non-cooperative self-assembly is provably weak

TAPDANCE's first publication, accepted to STOC 2017.

In this paper we show two results on the non-cooperative, aka temperature 1, abstract tile-assembly model. The first result shows that there is no tile set that at temperature 1 simulates all temperature 1 systems. In other words, the model is not intrinsic universal (unlike say the temperature 2 model). The second result shows that it is impossible to have a tile set that simulates a halting Turing machine in a bounded rectangle in the plane (but with a caveat: the simulator must place a special tile type on the right-hand side of the rectangle). Despite the caveat, this result shows that if temperature 1 can simulate Turing machines (we conjecture it can't) then it can not do so in a way that looks anything like any known tile-based simulations of Turing machines. So this paper gives two senses in which the cooperative model is provably more powerful than the non-cooperative model.

Pierre-Étienne Meunier, Damien Woods
The non-cooperative tile assembly model is not intrinsically universal or capable of bounded Turing machine simulation. [arxiv]