License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SAND.2022.14
URN: urn:nbn:de:0030-drops-159568
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15956/
Doty, David ;
Ong, Aaron
Simulating 3-Symbol Turing Machines with SIMD||DNA
Abstract
SIMD||DNA [Wang et al., 2019] is a model of DNA strand displacement allowing parallel in-memory computation on DNA storage. We show how to simulate an arbitrary 3-symbol space-bounded Turing machine with a SIMD||DNA program, giving a more direct and efficient route to general-purpose information manipulation on DNA storage than the Rule 110 simulation of Wang, Chalk, and Soloveichik [Wang et al., 2019]. We also develop software (https://github.com/UC-Davis-molecular-computing/simd-dna) that can simulate SIMD||DNA programs and produce SVG figures.
BibTeX - Entry
@InProceedings{doty_et_al:LIPIcs.SAND.2022.14,
author = {Doty, David and Ong, Aaron},
title = {{Simulating 3-Symbol Turing Machines with SIMD||DNA}},
booktitle = {1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
pages = {14:1--14:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-224-2},
ISSN = {1868-8969},
year = {2022},
volume = {221},
editor = {Aspnes, James and Michail, Othon},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15956},
URN = {urn:nbn:de:0030-drops-159568},
doi = {10.4230/LIPIcs.SAND.2022.14},
annote = {Keywords: DNA storage, strand displacement, parallel computation}
}
