Nicholas Schiefer: Computation and Construction in the Chemical Reaction Network-Controlled Tile Assembly Model

Tile-based self-assembly and chemical reaction networks provide two well-studied models of scalable molecular computation. Although tile self-assembly provides a powerful framework for describing Turing-universal self-assembling systems, assembly logic in tile self-assembly is localized, so that only the nearby environment can affect the process of self-assembly. We introduce a new model of tile-based self-assembly in which a well-mixed chemical reaction network interacts with self-assembling tiles to exert non-local control on the self-assembly process. We demonstrate the model's power for a variety of computation and construction tasks, including optimal-space simulation of Turing machines and constant-scale Kolmogorov-optimal construction of finite shapes. We also give a kinetic model of the CRN-TAM and analyze the time complexity of these tasks. Lastly, we explore possibilities for parallelism and illustrate its limits in the CRN-TAM. Our results suggest that controlled self-assembly provides additional algorithmic power over tile-only self-assembly, and that non-local control enhances our ability to perform computation and algorithmically self-assemble structures from small input programs.