Edit abstract data

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