The non-cooperative tile assembly model is not intrinsically universal or capable of bounded Turing machine simulation

The field of algorithmic self-assembly is concerned with the computational and expressive power of nanoscale self-assembling molecular systems. In the well-studied cooperative, or temperature 2, abstract tile assembly model it is known that there is a tile set to simulate any Turing machine and an intrinsically universal tile set that simulates the shapes and dynamics of any instance of the model, up to spatial rescaling. It has been an open question as to whether the seemingly simpler noncooperative, or temperature 1, model is capable of such behaviour. Here we show that this is not the case by showing that there is no tile set in the noncooperative model that is intrinsically universal, nor one capable of time-bounded Turing machine simulation within a bounded region of the plane.

Authors

• Pierre-Étienne Meunier
• Damien Woods

Keywords

• DNA computing
• Intrinsic universality
• Self-avoiding walks
• Tile self-assembly
• Turing machines