Computability in Europe 2006
Logical Approaches to Computational Barriers

Regular Talk:
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