Limitations of Self-Assembly at Temperature 1

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

[T1.pdf version in Theoretical Computer Science]