Thermodynamically Favorable Computation via Tile Self-assembly.

The recently introduced Thermodynamic Binding Networks (TBN) model wasdeveloped with the purpose of studying self-assembling systems by focusing ontheir thermodynamically favorable final states, and ignoring the kineticpathways through which they evolve. The model was intentionally developed toabstract away not only the notion of time, but also the constraints ofgeometry. Collections of monomers with binding domains which allow them to formpolymers via complementary bonds are analyzed to determine their final, stableconfigurations, which are those which maximize the number of bonds formed (i.e.enthalpy) and the number of independent components (i.e. entropy). In thispaper, we first develop a definition of what it means for a TBN to perform acomputation, and then present a set of constructions which are capable ofperforming computations by simulating the behaviors of space-bounded Turingmachines and boolean circuits. In contrast to previous TBN results, theseconstructions are robust to great variability in the counts of monomersexisting in the systems and the numbers of polymers that form in parallel.Although the Turing machine simulating TBNs are inefficient in terms of thenumbers of unique monomer types required, as compared to algorithmicself-assembling systems in the abstract Tile Assembly Model (aTAM), we thenshow that a general strategy of porting those aTAM system designs to TBNsproduces TBNs which incorrectly simulate computations. Finally, we present arefinement of the TBN model which we call the Geometric Thermodynamic BindingNetworks (GTBN) model in which monomers are defined with rigid geometries andform rigid bonds. Utilizing the constraints imposed by geometry, we thenprovide a GTBN construction capable of simulating Turing machines asefficiently as in the aTAM.