Difference between revisions of "Computability and Complexity in Self-Assembly"

From self-assembly wiki
Jump to navigation Jump to search
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 15: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

File

media:CCSA journal.pdf