Ph.D. Preliminary Exam - Scott Martin Summers

Date: 30 Apr, 2009
Time: 10:00 AM
Location: 223 Atanasoff Hall
Topic: Some Thoughts on Computation in Algorithmic Self-Assembly
Major Professor(s): Jack Lutz and James Lathrop


Abstract:

Self-assembly is a bottom-up process by which a small number of fundamental components automatically coalesce to form a target structure. In 1998, Winfree introduced the (abstract) Tile Assembly Model -- an effectivization of classical Wang tiling (1961 and 1962) -- as an over-simplified mathematical model of the DNA self-assembly pioneered by Seeman (1982). In the tile assembly model, the fundamental components are un-rotatable, but translatable square "tile types" whose sides are labeled with glue "colors" and "strengths." Two tiles that are placed next to each other interact if the glue colors on their abutting sides match, and they bind if the strength on their abutting sides matches with total strength at least a certain ambient "temperature," usually taken to be 1 or 2 (there are also several generalizations of the abstract model). The abstract tile assembly model has been refined over the years by Rothemund and Winfree (2000 and 2003) and Lathrop, Lutz and Summers (2007). Despite its over-simplification, the abstract tile assembly model is a goemetrically and computationally expressive model. For instance, Winfree (1998) proved that the abstract tile assembly model is universal in two or more spatial dimensions. This suggests that the process of self-assembly can be directed algorithmically.
A central question in algorhtmic self-assembly, due to Adleman (1999) is, "what are the assemblable shapes in the tile assembly model?" First, note that any finite shape X self-assembles (trivially) in a tile system having as many tile types as X has points. Rothemund and Winfree (1998) employed simple binary counters and Busy beaver Turing machines to self-assemble square shapes using efficient tile systems (i.e., tile systems having, asymptotically, fewer tile types than the square-root of the number of points in the target shape produced by said tile system). The efficient self-assembly of square shapes has also been studied by Doty (2009), Kao and Schweller (2008 and 2006), Becker, Rapaport and Remila (2006), and Aggarwal, Goldwasser, Kao and Schweller (2004), and Adleman, Cheng, Goel and Huang (2001). The optimal (and randomized) self- assembly of diamonds was addressed by Becker, Rapaport and Remila (2006), and Aggarwal, Goldwasser, Kao and Schweller (2004) exhibited optimal tile systems in which thin rectangles self-assemble. Soloveichik and Winfree (2007) discovered a beautiful theorem that bounds the tile complexity of a shape X above and below by the Kolomogorov complexity of a shape Y such that X is "scale-equivalent" to Y.
In this talk, we address Adleman's aforementioned question with respect to infinite shapes. First, we exhibit limitations of the tile assembly model with respect to the self-assembly of certain kinds of fractal shapes. We prove that no self-similar fractal self-assembles at temperature 1 in a locally deterministic tile assembly system, and that certain kinds of discrete self-similar fractals do not (strictly) self-assemble at any temperature. Additionally, we extend the fiber construction of Lathrop, Lutz and Summers (2007) to show that any discrete self-similar fractal belonging to a particular class of ``nice'' discrete self-similar fractals has a fibered version that strictly self-assembles in the tile assembly model. We then explore the impact of geometry on computability and complexity in self- assembly. We prove the following result: if a set of natural numbers is decidable, then it and its complement's "canonical two-dimensional representation" self-assemble. This leads to a novel characterization of decidable sets of natural numbers in terms of self-assembly. Next, we prove a new characterization of the set of all computably enumerable languages in terms of self-assembly. Specifically, we show that, for every computably enumerable set of natural numbers A, there exists a tile assembly system in which a simple, "quadratically spaced-out" version of A self-assembles along the positive horizontal axis. We use this construction to prove new undecidability results (with respect to languages of tile assembly systems), and also that every computably enumerable polynomial many-one degree strictly self-assembles. We also use the Time Hierarchy Theorem to prove that a particular family of decidable sets of integer lattice points do not self-assemble.
Finally, we show that, if a set X of integer lattice points self-assembles at temperature 1 in a deterministic tile assembly system satisfying a natural condition known as "pumpability," then X is a finite union of semi-doubly periodic sets. This proves that only the most simple of infinite shapes and patterns can be constructed using pumpable temperature 1 tile assembly systems, and gives evidence for the thesis that temperature 2 or higher is required to carry out general-purpose computation in a tile assembly system. Finally, we show that general-purpose computation \emph {is} possible at temperature 1 if negative glue strengths are allowed in the tile assembly model.
Open problems are also discussed.