Limitations of Self-Assembly at Temperature One (extended abstract)

David Doty
Matthew J. Patitz
Scott M. Summers

We prove that if a subset X of the integer Cartesian plane weakly self-assembles at temperature 1 in a deterministic (Winfree) tile assembly system satisfying a natural condition known as *pumpability*, then X is a finite union of doubly periodic sets. This shows that only the most simple of infinite shapes and patterns can be constructed using pumpable temperature 1 tile assembly systems, and gives strong evidence for the thesis that temperature 2 or higher is required to carry out general-purpose computation in a tile assembly system. Finally, we show that general-purpose computation *is* possible at temperature 1 if negative glue strengths are allowed in the tile assembly model.

In Turlough Neary, Damien Woods, Tony Seda and Niall Murphy: Proceedings International Workshop on The Complexity of Simple Programs (CSP 2008), Cork, Ireland, 6-7th December 2008, Electronic Proceedings in Theoretical Computer Science 1, pp. 67–69.
Published: 25th June 2009.

ArXived at: http://dx.doi.org/10.4204/EPTCS.1.6 bibtex PDF

Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org