National University of Ireland Maynooth
Six Tiles : From Collatz Sequences to Algorithmic DNA Origami
Abstract
dc:description.abstractWe tile a path from the theoretical world of Collatz sequences, which are fascinating, seemingly undecipherable mathematical objects, to the experimental wet lab world of algorithmic DNA origami, which is our proposed technique to run algorithms using self-assembling DNA nanostructures. The common thread throughout these seemingly unrelated worlds is the use of tile self-assembly models to reason about the problem at hand. In the case of Collatz sequences (also known as 3x+1 sequences), we study 6 Wang tiles, which give this thesis its name, that assemble Collatz sequences in tilings. These Collatz tilings provide a microscope for studying Collatz sequences symbolically in many bases (base 2, 3, 6, and more) and allow us to interpret known results in our 2D tiling framework, as well as partially characterising the complexity of predicting Collatz iterations, Chapter 1. We then use these 6 tiles to visualise a conjecture by Erdős on powers of two that we encode as the halting problem (from blank tape) of a 15-state 2-symbol Turing machine. This construction implies that knowing the busy beaver value BB(15) is at least as hard as solving Erdős’ conjecture, which seems to put BB(15) out of reach since the conjecture has been open for decades, Chapter 2. We go on to show that our 6 tiles can simulate arbitrary Boolean circuits in a model of tile assembly that we introduce: the Maze-Walking Tile Assembly Model. This is when our journey starts entering the realm of wet lab experiments, as we argue that our Maze-Walking TAM is suited to DNA nanostructure implementation, Chapter 3. We make this claim concrete in Chapter 4 by introducing the Scaffolded DNA Computer, a thermodynamically favoured model of computation very close in spirit to the Maze-Walking TAM. In the wet lab we implement eight DNA-based programs for this computer (corresponding to over 100 DNA program executions), including a 7-bit adder running within a DNA origami, or, as we call it, an algorithmic DNA origami.
Degree
thesis:*- Name dc:type.qualificationname
- phd
- Level dc:type.qualificationlevel
- doctoral
- Grantor dc:publisher.institution
- National University of Ireland Maynooth
- Year dc:date.issued
- 2023
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Stérin, Tristan
Rights
- Language dc:language
- en