English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The field of algorithmic self-assembly is concerned with the computationaland expressive power of nanoscale self-assembling molecular systems. In thewell-studied cooperative, or temperature 2, abstract tile assembly model it isknown that there is a tile set to simulate any Turing machine and anintrinsically universal tile set that simulates the shapes and dynamics of anyinstance of the model, up to spatial rescaling. It has been an open question asto whether the seemingly simpler noncooperative, or temperature 1, model iscapable of such behaviour. Here we show that this is not the case, by showingthat there is no tile set in the noncooperative model that is intrinsicallyuniversal, nor one capable of time-bounded Turing machine simulation within abounded region of the plane.  Although the noncooperative model intuitively seems to lack the complexityand power of the cooperative model it was not obvious how to prove this. Onereason is that there have been few tools to analyse the structure ofcomplicated paths in the plane. This paper provides a number of such tools. Asecond reason is that almost every obvious and small generalisation to themodel (e.g. allowing error, 3D, non-square tiles, signals/wires on tiles, tilesthat repel each other, parallel synchronous growth) endows it with greatcomputational, and sometimes simulation, power. Our main results show that allof these generalisations provably increase computational and/or simulationpower. Our results hold for both deterministic and nondeterministicnoncooperative systems. Our first main result stands in stark contrast with thefact that for both the cooperative tile assembly model, and for 3Dnoncooperative tile assembly, there are respective intrinsically universaltilesets. Our second main result gives a new technique (reduction tosimulation) for proving negative results about computation in tile assembly.

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