Open Access. Powered by Scholars. Published by Universities.®
University of Arkansas, Fayetteville
Computer Science and Computer Engineering Undergraduate Honors Theses
- Discipline
Articles 1 - 2 of 2
Full-Text Articles in Theory and Algorithms
Universal Computation Using Self-Assembling, Crisscross Dna Slats, Jackson S. Bullard
Universal Computation Using Self-Assembling, Crisscross Dna Slats, Jackson S. Bullard
Computer Science and Computer Engineering Undergraduate Honors Theses
I first give a brief introduction to formal models of computation. I then present three different approaches for computation in the aTAM. I later detail generating systems of crisscross slats given an arbitrary algorithm encoded in the form of a Turing machine. Crisscross slats show potential due to their high levels of cooperativity, so it is hoped that implementations utilizing slats are more robust to various growth errors compared to the aTAM. Finally, my software converts arbitrary crisscross slat systems into various physical representations that assist in analyzing their potential to be realized in experiments.
Computational Complexity Of Determining The Rigidity Of Ftam Assemblies, Ian Perkins
Computational Complexity Of Determining The Rigidity Of Ftam Assemblies, Ian Perkins
Computer Science and Computer Engineering Undergraduate Honors Theses
In this paper, we discuss a tile-based self-assembly model called the Folding Tile Assembly Model (FTAM). We briefly define what makes the FTAM unique in its ability to have folding 2D tiles. We also discuss the difficulty of determining the computational complexity of certain FTAM properties despite it being simpler for less dynamic models. Specifically, we discuss the property of rigidity in FTAM assemblies by devising a simple definition of rigidity, so that it is easier to determine its complexity. We use a reduction between an assembly and a 3SAT instance along with a series of proofs to give a …