Logical Approaches to Computational Barriers

Computability and Complexity in Self-Assembly

Author(s): |
James Lathrop, Jack H. Lutz, Matthew J. Patitz and Scott M. Summers |

Slot: |
Array, 11:40-12:00, col. 1 |

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 Z x Z. Our first main theorem says that there is a roughly quadratic function f such that a set A of positive integers is computably enumerable if and only if the set X_A = { (f(n), 0) | 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 subsets D of Z x 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 T_M, together with a proof that T_M carries out concurrent simulations of M on all positive integer inputs.

websites: Arnold Beckmann | 2008-05-18 |