View source for The Non-cooperative Tile Assembly Model Is Not Intrinsically Universal or Capable of Bounded Turing Machine Simulation

{{PaperTemplate
|title=The Non-cooperative Tile Assembly Model Is Not Intrinsically Universal or Capable of Bounded Turing Machine Simulation
|abstract=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 simulateany  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. Although the noncooperative model intuitively seems to lack the complexity and power of the cooperative model it has been exceedingly hard to prove this.  One reason is that there have been few tools to analyse the structure of complicated paths in the plane.  This paper provides a number of such tools.  A second reason is that almost every obvious and small generalisation 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 generalisations provably increase computational and/or simulation power.  Our results hold for both deterministic and nondeterministic noncooperative systems.  Our first main result stands in stark contrast with the fact that for both the cooperative tile assembly model, and for 3D noncooperative tile assembly, there are respective intrinsically universal tilesets.  Our second main result  gives  a  new  technique  (reduction  to  simulation)  for  proving  negative  results  about computation in tile assembly. 

|authors= Pierre- ́Etienne Meunier, Damien Woods
|date=2017/01/02
|file=https://arxiv.org/pdf/1702.00353 arXiv
}}