Difference between revisions of "Limitations of Self-Assembly at Temperature 1"

From self-assembly wiki
Jump to navigation Jump to search
Line 10: Line 10:
 
temperature 1 in a pumpable tile assembly system.
 
temperature 1 in a pumpable tile assembly system.
 
|authors=David Doty, Matthew J. Patitz, and Scott M. Summers
 
|authors=David Doty, Matthew J. Patitz, and Scott M. Summers
|file=[T1.pdf version in Theoretical Computer Science]
+
|file=[http://self-assembly.net/mpatitz/papers/T1.pdf version in Theoretical Computer Science]
 
}}
 
}}

Revision as of 00:24, 4 December 2011

Published on:

Abstract

We prove that if a set \(X \subseteq \mathbb{Z}^2\) weakly self-assembles at temperature 1 in a deterministic (Winfree) tile assembly system satisfying a natural condition known as pumpability, then \(X\) is a semilinear set. This shows that only the most simple of infinite shapes and patterns can be constructed using pumpable temperature 1 tile assembly systems, and gives evidence for the thesis that temperature 2 or higher is required to carry out general-purpose computation in a deterministic two-dimensional tile assembly system. We employ this result to show that, unlike the case of temperature 2 self-assembly, no discrete self-similar fractal weakly self-assembles at temperature 1 in a pumpable tile assembly system.

Authors

David Doty, Matthew J. Patitz, and Scott M. Summers

File

version in Theoretical Computer Science