Difference between revisions of "Computability and Complexity in Self-Assembly"
m |
|||
| (3 intermediate revisions by 2 users not shown) | |||
| 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<br \> |
| − | is computably enumerable if and only if the set $X_A = | + | $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 |
| − | 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. Our first main theorem is established by an explicit translation of an arbitrary Turing machine M to |
| − | |||
| − | 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 | a modular tile assembly system TM, together with a proof that TM carries out concurrent simulations of | ||
M on all positive integer inputs. | M on all positive integer inputs. | ||
|authors=James I. Lathrop, Jack H. Lutz, Matthew J. Patitz, and Scott M. Summers | |authors=James I. Lathrop, Jack H. Lutz, Matthew J. Patitz, and Scott M. Summers | ||
| − | |file=[[media:CCSA journal.pdf]] | + | |date=2010/04/20 |
| + | |file=[[media:CCSA journal.pdf | Computability and Complexity in Self-Assembly.pdf]] | ||
}} | }} | ||
Latest revision as of 12:29, 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\)) \(\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
