Difference between revisions of "Computability and Complexity in Self-Assembly"
Jump to navigation
Jump to search
m |
|||
| Line 4: | Line 4: | ||
of nanoscale self-assembly. We work in the two-dimensional tile assembly model, i.e., in the discrete | 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 | 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}^+$ | + | that a set $A \subseteq \mathbb{Z}^+$ is computably enumerable if and only if the set $X_A$ = {($f(n)$, $0$)$ | $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 |
| − | is computably enumerable if and only if the set $X_A = | ||
| − | 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 | 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. | sense. | ||
Revision as of 13:22, 22 June 2021
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\))\(
Authors
James I. Lathrop, Jack H. Lutz, Matthew J. Patitz, and Scott M. Summers
