Difference between revisions of "Computability and Complexity in Self-Assembly"
Jump to navigation
Jump to search
(Created page with "{{PaperTemplate |title=Computability and Complexity in Self-Assembly |abstract=This paper explores the impact of geometry on computability and complexity in Winfree’s model
of...") |
|||
| 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 | ||
| − | |file=CCSA journal.pdf | + | |file=[[media:CCSA journal.pdf]] |
}} | }} | ||
Revision as of 13:31, 4 December 2011
Published on:
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
