View source for Intrinsic Universality of the aTAM

An intrinsically universal model is one which contains some system ''U'', such that for any arbitrary system ''T'' within that model, ''U'' can be given a starting condition based on ''T'' such that ''U'' will then completely [[simulate]] the behavior of ''T''.  That is, ''U'' will mimic all behaviors of ''T'', but at a re-scaling in which each ''n × n'' block within ''U'', for some $n \in \mathbb{N}$, can be mapped to a single element of ''T''.  Cellular automata and Turing machines are both examples of models which are intrinsically universal.  While an aTAM system can be designed to simulate an arbitrary Turing machine, which could computationally simulate an arbitrary aTAM system, another interesting question was whether or not the aTAM is intrinsically universal, or:  Is there a single tile set which can be used to simulate the behavior of any arbitrary aTAM system?  Essentially, if the tiles of this "universal" tile set could be arranged to form a seed structure such that that structure contains an encoding of some other aTAM system, say $\mathcal{T}$, could additional copies of tiles from the universal tile set attach to grow into an assembly which simulates the system $\mathcal{T}$? Of course, the simulation would be a scaled up version of the original system, but it must be the case that every behavior that $\mathcal{T}$ is capable of, the simulating system is also capable of.  Preliminary work by Doty, Lutz, Patitz, Summers, and Woods in <ref name=USA /> showed that for a constrained set of aTAM systems, namely those in which all tiles bind with exactly strength $\tau$ and there are no glue mismatches between adjacent tile edges, that class is intrinsically universal.  Furthermore, it was later shown by Doty, Lutz, Patitz, Schweller, Summers, and Woods in <ref name=IUSA /> that the entire, unconstrained class of aTAM systems is intrinsically universal.  In fact, they demonstrated a tile set ''U'' and a method for using the definition of an arbitrary aTAM system $\mathcal{T}$ of ''any'' temperature to form a seed structure for ''U'' so that the system with that seed, the tiles from ''U'', and at temperature 2, can simulate $\mathcal{T}$.  Thus, a single tile set in a properly seeded system at temperature 2 can simulate the behavior of ''any'' aTAM system at ''any'' temperature.

The previous result shows a powerful symmetry to the aTAM, since there is a system within it that can behave exactly like any other system within it. In <ref name=IUNeedsCoop />, Meunier, Patitz, Summers, Theyssier, Winslow, and Woods showed that the temperature 2 parameter for systems using the intrinsically universal tile set is in fact a lower bound.  They showed that no aTAM tile set exists which can simulate arbitrary aTAM systems of temperature >1, while operating in a system of temperature 1, proving that the cooperative behavior provided by temperature 2 self-assembly can not be simulated at temperature 1.  Further, their impossibility result extends to 3D, showing that even 3D temperature 1 aTAM systems cannot simulate 2D temperature 2 aTAM systems, which is contrasted with the facts that 3D temperature 1 systems are capable of universal computation (see [[The influence of temperature]]), and the second result of <ref name=IUNeedsCoop /> shows that 3D temperature 1 systems can simulate arbitrary 2D temperature 1 systems.  These results especially emphasize the fact that the power to perform universal computation does not imply the power to simulate arbitrary behaviors of algorithmic self-assembly.

==References==
<references>

<ref name =USA><bibtex>
@inproceedings{USA,
  author = "David Doty and Jack H. Lutz and Matthew J. Patitz and Scott M. Summers and Damien Woods",
  title = "Intrinsic Universality in Self-Assembly",
 booktitle = "Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science",
  year = 2009,
pages = "275--286"
}
</bibtex></ref>

<ref name =IUSA><bibtex>
@inproceedings{IUSA,
 author    = {David Doty and
               Jack H. Lutz and
               Matthew J. Patitz and
               Robert T. Schweller and
               Scott M. Summers and
               Damien Woods},
 title     = {The tile assembly model is intrinsically universal},
 booktitle = {Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science},
 series = {FOCS 2012},
 year = {2012},
 location = {New Brunswick, New Jersey},
}
</bibtex></ref>

<ref name =IUNeedsCoop><bibtex>
@techreport{IUNeedsCoop,
  author    = {Pierre-Etienne Meunier and
               Matthew J. Patitz and
               Scott M. Summers and
               Guillaume Theyssier and
               Andrew Winslow and
               Damien Woods},
  title     = {Intrinsic universality in tile self-assembly requires cooperation},
  institution = {Computing Research Repository},
  number    = {1304.1679},
  year      = {2013},
  url        = {http://arxiv.org/abs/1304.1679},
}

</bibtex></ref>

</references>

[[Category:Results in the aTAM]]