Computational aspects of dna self-assembly systems at temperature 1

In this thesis, we investigate the computational power of some variants of Winfree's abstract Tile Assembly Model (aTAM) at Temperature 1 [43]. Although aTAM at temperatures higher than 1 are proved to be Turing Universal, i.e. they can simulate an arbitrary Turing Machine [43], the computational power of aTAM at temperature 1 is still an open question. It is known that some modifications of aTAM are indeed Turing Universal at temperature 1 [11, 30]. In this thesis, we first show that two variants of aTAM, namely the Staged Tile Assembly Model and Step-wise Tile Assembly Model at Temperature 1, are also Turing Universal. Next, we discuss the computational power of the self-assembly with triangular tiles and hexagonal tiles, respectively. We prove that these models can simulate arbitrary systems under aTAM and vice versa, and consequently, they have the same computational power as aTAM.