Computability and Complexity in Self-Assembly
Published on: 2010/04/20
Abstract
This paper explores the impact of geometry on computability and complexity in Winfree’s model
of nanoscale self-assembly. We work in the two-dimensional tile assembly model, i.e., in the discrete
Euclidean plane \(\mathbb{Z} \times \mathbb{Z}\). Our first main theorem says that there is a roughly quadratic function \(f\) such
that a set \(A \subseteq \mathbb{Z}^+\) is computably enumerable if and only if the set
\(X_A\) = {(\(f(n)\), \(0\)) \(\mid n\) \(\in \)A} – a simple representation of \(A\) as a set of points on the x-axis – self-assembles in Winfree’s sense. In contrast, our
second main theorem says that there are decidable sets \(D \subseteq \mathbb{Z} \times \mathbb{Z}\) that do not self-assemble in Winfree’s
sense. Our first main theorem is established by an explicit translation of an arbitrary Turing machine M to
a modular tile assembly system TM, together with a proof that TM carries out concurrent simulations of
M on all positive integer inputs.
Authors
James I. Lathrop, Jack H. Lutz, Matthew J. Patitz, and Scott M. Summers
