Difference between revisions of "Open Problems"
| Line 8: | Line 8: | ||
<br> | <br> | ||
<br> | <br> | ||
| − | 3) Is the class of [[Directed Tile Assembly Systems | directed]] [[Abstract Tile Assembly Model (aTAM) | aTAM]] systems [[Intrinsic Universality | intrinsically universal for itself? | + | 3) Is the class of [[Directed Tile Assembly Systems | directed]] [[Abstract Tile Assembly Model (aTAM) | aTAM]] systems [[Intrinsic Universality | intrinsically universal]] for itself? |
Revision as of 11:33, 27 May 2014
The following are a list of open problems in self-assembly:
1) In his 1998 thesis [1], Winfree showed that the class of directed aTAM systems at temperature 2 is computationally universal, and in [2] Cook et al. showed that undirected temperature 1 aTAM systems could perform computations with a given amount of certainty and that in 2 planes directed aTAM temperature 1 systems were computationally universal. Is the class of directed aTAM systems at temperature 1 in the plane computationally universal? In [3] Doty, Patitz, and Summers provide deep insights into this question.
2) In [4], Doty et al. introduced a model known as the fuzzy temperature model and showed that in this model n by n squares could efficiently self-assemble. Can systems in this model also perform general computation?
3) Is the class of directed aTAM systems intrinsically universal for itself?
References
- ↑
Erik Winfree - Algorithmic Self-Assembly of DNA
- Ph.D. Thesis, California Institute of Technology , June 1998
- BibtexAuthor : Erik Winfree
Title : Algorithmic Self-Assembly of DNA
In : Ph.D. Thesis, California Institute of Technology -
Address :
Date : June 1998
- ↑
Matthew Cook, Yunhui Fu, Robert T. Schweller - Temperature 1 Self-Assembly: Deterministic Assembly in 3{D} and Probabilistic Assembly in 2{D}
- SODA 2011: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms ,2011
- BibtexAuthor : Matthew Cook, Yunhui Fu, Robert T. Schweller
Title : Temperature 1 Self-Assembly: Deterministic Assembly in 3{D} and Probabilistic Assembly in 2{D}
In : SODA 2011: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms -
Address :
Date : 2011
- ↑
David Doty, Matthew J. Patitz, Scott M. Summers - Limitations of Self-Assembly at Temperature 1
- Theoretical Computer Science 412:145-158,2011
- BibtexAuthor : David Doty, Matthew J. Patitz, Scott M. Summers
Title : Limitations of Self-Assembly at Temperature 1
In : Theoretical Computer Science -
Address :
Date : 2011
- ↑
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
- BibtexAuthor : 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
