Difference between revisions of "Computability and Complexity in Self-Assembly"
Jump to navigation
Jump to search
Wiki admin (talk | contribs) |
|||
| Line 14: | Line 14: | ||
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 | ||
| + | |date=2010/04/20 | ||
|file=[[media:CCSA journal.pdf]] | |file=[[media:CCSA journal.pdf]] | ||
}} | }} | ||
Revision as of 14:05, 23 January 2012
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
