Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR08-031 | 14th January 2008 00:00

Computability and Complexity in Self-Assembly

RSS-Feed

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 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 =3D {
(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.



ISSN 1433-8092 | Imprint