Applications of the theory of computation to nanoscale self-assembly.

摘要

This thesis applies the theory of computing to the theory of nanoscale self-assembly, to explore the ability -- and under certain conditions, the inability -- of molecules to automatically arrange themselves in computationally sophisticated ways. In particular, we investigate a model of molecular self-assembly known as the abstract Tile Assembly Model (aTAM), in which different types of square "tiles" represent molecules that, through the interaction of highly specific binding sites on their four sides, can automatically assemble into larger and more elaborate structures.;We investigate the possibility of using the inherent randomness of sampling different tiles in a well-mixed solution to drive selection of random numbers from a finite set, and explore the tradeoff between the uniformity of the imposed distribution and the size of structures necessary to process the sampled tiles.;We then show that the inherent randomness of the competition of different types of molecules for binding can be exploited in a different way. By adjusting the relative concentrations of tiles, the structure assembled by a tile set is shown to be programmable to a high precision, in the following sense. There is a single tile set that can be made to assemble a square of arbitrary width with high probability, by setting the concentrations of the tiles appropriately, so that all the information about the square's width is "learned" from the concentrations by sampling the tiles.;Based on these constructions, and those of other researchers, which have been completely implemented in a simulated environment, we design a high-level domain-specific "visual language" for implementing complex constructions in the aTAM. This language frees the implementer of an aTAM construction from many low-level and tedious details of programming and, together with a visual software tool that directly implements the basic operations of the language, frees the implementer from almost any programming at all.;Finally, after showing these positive results, we turn our attention to negative results and investigate inherent limitations in the aTAM at "temperature 1", meaning roughly that all bonds in the system have sufficient strength to permanently attach tiles without help from other bonds (i.e., the temperature is too low to "shake off" any tiles, even those connected by a single bond). Specifically, we show that at temperature 1, a wide class of deterministic tile sets (those satisfying a natural condition known as "pumpability") form only the most computationally simple structures (specifically, semilinear sets of integer coordinates, equivalently those sets definable in Presburger arithmetic), and in particular are strictly less powerful than the computationally universal temperature 2 tile assembly model. We leave as an open question whether all deterministic temperature 1 tile sets are in fact pumpable.