View source for Intrinsic Universality in the 2HAM

The existence of a single tile set which can be configured to simulate any aTAM system is discussed in [[Intrinsic universality of the aTAM]].  In contrast, in <ref name=2HAMIU /> Demaine, Patitz, Rogers, Schweller, Summers, and Woods proved that no such tile set exists for the 2HAM.  More precisely, they showed that for every 2HAM system at temperature ''τ'', there exists some system at temperature ''τ+1'' which cannot be simulated by it.  Their proof is based upon the ability of the 2HAM to simultaneously utilize the binding of multiple glues positioned on tiles arbitrarily far apart.  They describe a system which produces assemblies which look like ladders that each have ''τ+1'' rungs and form in such a way that each half of a ladder with all ''τ+1'' half-rungs must fully form before binding to a complementary half-ladder to form a full ladder.  They then prove that any system whose temperature is ''< τ+1'' can't simulate such a system, since it would have to "fake" the binding of one or more rungs and must therefore also be able to form ladders which have ''<τ+1'' rungs.  Since the original system couldn't form these, the simulator can't correctly simulate it.

While the entire 2HAM is not intrinsically universal, in <ref name=2HAMIU /> they went on to show how, for each individual ''τ>1'', the class of 2HAM systems at ''τ'' is intrinsically universal.  This means that for each temperature ''τ'', there exists a single tile set which can simulate all 2HAM systems at temperature ''τ''.  Their constructions showed a variety of tradeoffs in the number of unique input supertiles required for each simulation, their sizes, and the scale factor of the simulations.  For their final result, they exhibited a construction which provides a single tile set for each ''τ'' which requires no input supertiles and which simultaneously and in parallel simulates ''every'' 2HAM system at temperature ''τ''.

As a corollary to their results related to intrinsic universality in the 2HAM, the authors of <ref name=2HAMIU /> show that within the 2HAM there is an infinite set of infinite hierarchies of 2HAM systems with strictly increasing power within each hierarchy, which creates a much more complex landscape than the fully unifying result of <ref name=IUSA /> for the aTAM!

==References==
<references>

<ref name =2HAMIU><bibtex>
@incollection{2HAMIU,
year={2013},
title={The two-handed tile assembly model is not intrinsically universal},
author = {Erik D. Demaine and Matthew J. Patitz and Trent A. Rogers and Robert T. Schweller and Scott M. Summers and Damien Woods},
booktitle={Proceedings of the Fortieth International Colloquium on Automata, Languages and Programming (ICALP 2013)},
note = {to appear},
}
</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>
</references>

[[Category: 2HAM Results]]
[[Category: Simulation in Self-assembly]]
[[Category:Self-assembly]]