Computability and Complexity in Self-Assembly

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

File

media:CCSA journal.pdf