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.