Ph.D. Preliminary Exam - Matthew Patitz

Date: 18 Nov, 2008
Time: 9:00 AM
Location: 223 Atanasoff Hall
Topic: Self-Assembly of Infinite Structures
Major Professor(s): Jack Lutz


Abstract:

The simplest mathematical model of nanoscale self-assembly is the Tile Assembly Model (TAM), an effectivization of Wang tiling that was introduced by Erik Winfree in 1998 and refined by Rothemund and Winfree in 2001. As a basic model for the self-assembly of matter, the TAM has allowed researchers to explore an assortment of avenues into both laboratory-based and theoretical approaches to designing systems that self-assemble into desired shapes or autonomously coalesce into patterns that, in doing so, perform computations.

Actual physical experimentation has driven lines of research involving kinetic variations of the TAM to deal with molecular concentrations, reaction rates, etc., as well as work focused on error prevention and error correction. Divergent from but supplementary to the laboratory work, much theoretical research involving the TAM has also been carried out. Interesting questions concerning the minimum number of tile types required to self-assemble shapes, different notions of running time and bounds thereof, variations of the model where temperature values are intentionally fluctuated and the ensuing benefits and tradeoffs, and systems for generating randomized shapes or approximations of target shapes have all been investigated.

This is just a small sampling of the theoretical work in the field of algorithmic self-assembly. However, as different as they may be, the above mentioned lines of research share a common thread. They all tend to focus on the self-assembly of finite structures. Clearly, for the experimental research, this is a necessary limitation. Further, if the eventual goal of most of the theoretical research is to enable the development of fully functional, real world self-assembly systems, a valid question is: ``Why care about anything but finite structures?'' This is the question we address in this presentation.

We survey the collection of our recent findings related to the self-assembly of infinite structures in the TAM. As a theoretical exploration of the TAM, this collection of results seeks to define absolute limitations on the classes of shapes that self-assemble. These results also help to explore how fundamental aspects of the TAM, such as the inability of spatial locations to be reused and their immutability, affect and limit the constructions and computations that are achievable.

In addition to providing concise statements and intuitive descriptions of these results, we also present a line of software tools, including a TAM simulator, which we have developed and made freely available, and which can be used to reproduce and perhaps extend our results.