Computational aspects of dna self-assembly systems at temperature 1

Resource type
Thesis type
(Thesis) M.Sc.
Date created
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.
Copyright statement
Copyright is held by the author.
The author granted permission for the file to be printed and for the text to be copied and pasted.
Scholarly level
Supervisor or Senior Supervisor
Thesis advisor: Stacho, Ladislav
Thesis advisor: Manuch, Jan
Member of collection
Attachment Size
etd7835_BBehsaz.pdf 2.16 MB