TR08-031 Authors: James I. Lathrop, Jack H. Lutz, Matthew J. Patitz, Scott M. Summers

Publication: 18th March 2008 17:35

Downloads: 2923

Keywords:

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.