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 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 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 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 for the aTAM!