Fuzzy Temperature Fault Tolerance

From self-assembly wiki
Revision as of 11:08, 11 July 2013 by \('"2\)'"7
(\(1) \)2 | \(3 (\)4) | \(5 (\)6)
Jump to navigation Jump to search

Recall that the 2HAM allows for the nucleation of an assembly by any pair of tiles with binding strength equal to the temperature. It therefore seems that self-assembly in the 2HAM at temperature 1, where every pair of matching glues on any pair of tile edges is sufficient to initiate the growth of an assembly, is doomed to either 1. make nothing but the most simple of periodic structures, or 2. require tile complexity equivalent to the number of points in the desired shape. However, temperature 2 assembly in the 2HAM is computationally universal, so, as in the aTAM, the question becomes: is temperature 1 provably strictly weaker? While that remains an open question, in [1] Doty, Patitz, Reishus, Schweller, and Summers introduced a variation to the model where the temperature parameter isn't fixed, but instead can drift between 1 and 2, staying at one or the other for arbitrarily long. However, there is a guarantee that the temperature will eventually at some point return to 2 and stay there for arbitrarily long. They called this model fuzzy temperature, and showed that they could develop systems which exhibited strong fault-tolerance in such conditions (meaning that they were guaranteed to always produce the correct assembly) while building n × n squares using only \(O(\log n)\) tile types. To obtain this fault tolerance, the construction had to ensure that any unintended growth that occurred during a phase of temperature 1 could not become stably "locked in" at temperature 2, meaning that they would always have to dissolve when the temperature raised.

References

  1. David Doty, Matthew J. Patitz, Dustin Reishus, Robert T. Schweller, Scott M. Summers - Strong Fault-Tolerance for Self-Assembly with Fuzzy Temperature
    Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010) pp. 417--426,2010
    Bibtex
    Author : David Doty, Matthew J. Patitz, Dustin Reishus, Robert T. Schweller, Scott M. Summers
    Title : Strong Fault-Tolerance for Self-Assembly with Fuzzy Temperature
    In : Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010) -
    Address :
    Date : 2010