Back to search

National University of Ireland Maynooth

Six Tiles : From Collatz Sequences to Algorithmic DNA Origami

Abstract

dc:description.abstract

We 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

Chain of custody

source
Harvested from
National University of Ireland - Maynooth
Base URL
mural.maynoothuniversity.ie/cgi/oai2
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
related terms
citation

Stérin, Tristan. Six Tiles : From Collatz Sequences to Algorithmic DNA Origami. doctoral thesis, National University of Ireland Maynooth, 2023.