The Non-cooperative Tile Assembly Model Is Not Intrinsically Universal or Capable of Bounded Turing Machine Simulation
Published on: 2017/01/02
Abstract
The field of algorithmic self-assembly is concerned with the computational and expressivepower of nanoscale self-assembling molecular systems. In the well-studied cooperative, ortemperature 2, abstract tile assembly model it is known that there is a tile set to simulateany Turing machine and an intrinsically universal tile set that simulates the shapes anddynamics of any instance of the model, up to spatial rescaling. It has been an open questionas to whether the seemingly simpler noncooperative, or temperature 1, model is capable ofsuch behaviour. Here we show that this is not the case, by showing that there is no tile setin the noncooperative model that is intrinsically universal, nor one capable of time-boundedTuring machine simulation within a bounded region of the plane.Although the noncooperative model intuitively seems to lack the complexity and powerof the cooperative model it has been exceedingly hard to prove this. One reason is that therehave been few tools to analyse the structure of complicated paths in the plane. This paperprovides a number of such tools. A second reason is that almost every obvious and smallgeneralisation to the model (e.g. allowing error, 3D, non-square tiles, signals/wires on tiles,tiles that repel each other, parallel synchronous growth) endows it with great computational,and sometimes simulation, power. Our main results show that all of these generalisationsprovably increase computational and/or simulation power. Our results hold for both deter-ministic and nondeterministic noncooperative systems. Our first main result stands in starkcontrast with the fact that for both the cooperative tile assembly model, and for 3D nonco-operative tile assembly, there are respective intrinsically universal tilesets. Our second mainresult gives a new technique (reduction to simulation) for proving negative results aboutcomputation in tile assembly.
Authors
Pierre- ́Etienne Meunier, Damien Woods
