LIPIcs.SAND.2022.14.pdf
- Filesize: 0.93 MB
- 15 pages
Document
Simulating 3-Symbol Turing Machines with SIMD||DNA
Authors
David Doty 
,
-
Part of:
Volume:
1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Algorithmic Foundations of Dynamic Networks (SAND) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-04-29
File
Document Identifiers
Author Details
Cite AsGet BibTex
David Doty and Aaron Ong. Simulating 3-Symbol Turing Machines with SIMD||DNA. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 14:1-14:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SAND.2022.14
https://doi.org/10.4230/LIPIcs.SAND.2022.14
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.
Subject Classification
ACM Subject Classification
- Theory of computation → Models of computation
Keywords
- DNA storage
- strand displacement
- parallel computation
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
James Bornholt, Randolph Lopez, Douglas M Carmean, Luis Ceze, Georg Seelig, and Karin Strauss. A DNA-based archival storage system. In ASPLOS 2016: Proceedings of the Twenty-First International Conference on Architectural Support for Programming Languages and Operating Systems, pages 637-649, 2016.
- Tonglin Chen, Arnav Solanki, and Marc Riedel. Parallel Pairwise Operations on Data Stored in DNA: Sorting, Shifting, and Searching. In DNA 27: 27th International Conference on DNA Computing and Molecular Programming, volume 205, pages 11:1-11:21, 2021. URL: https://doi.org/10.4230/LIPIcs.DNA.27.11.
-
George M Church, Yuan Gao, and Sriram Kosuri. Next-generation digital information storage in DNA. Science, 337(6102):1628-1628, 2012.
-
Matthew Cook. Universality in elementary cellular automata. Complex systems, 15(1):1-40, 2004.
-
Turlough Neary and Damien Woods. P-completeness of cellular automaton Rule 110. In ICALP 2006: International Colloquium on Automata, Languages, and Programming, pages 132-143. Springer, 2006.
-
Turlough Neary and Damien Woods. Small fast universal Turing machines. Theoretical Computer Science, 362(1-3):171-195, 2006.
-
Lee Organick, Siena Dumas Ang, Yuan-Jyue Chen, Randolph Lopez, Sergey Yekhanin, Konstantin Makarychev, Miklos Z Racz, Govinda Kamath, Parikshit Gopalan, Bichlien Nguyen, Christopher N Takahashi, Sharon Newman, Hsing-Yeh Parker, Cyrus Rashtchian, Kendall Stewart, Gagan Gupta, Robert Carlson, John Mulligan, Douglas Carmean, Georg Seelig, Luis Ceze, and Karin Strauss. Random access in large-scale DNA data storage. Nature Biotechnology, 36(3):242, 2018.
-
Lulu Qian, David Soloveichik, and Erik Winfree. Efficient Turing-universal computation with DNA polymers. In International Workshop on DNA-Based Computers, pages 123-140. Springer, 2010.
-
Georg Seelig, David Soloveichik, David Yu Zhang, and Erik Winfree. Enzyme-free nucleic acid logic circuits. Science, 314(5805):1585-1588, 2006.
- SIMD||DNA simulator. Source code: https://github.com/UC-Davis-molecular-computing/simd-dna, 2021.
-
S Kasra Tabatabaei, Boya Wang, Nagendra Bala Murali Athreya, Behnam Enghiad, Alvaro Gonzalo Hernandez, Christopher J Fields, Jean-Pierre Leburton, David Soloveichik, Huimin Zhao, and Olgica Milenkovic. DNA punch cards for storing data on native DNA sequences via enzymatic nicking. Nature Communications, 11(1):1-10, 2020.
-
Boya Wang, Cameron Chalk, and David Soloveichik. SIMD||DNA: Single instruction, multiple data computation with DNA strand displacement cascades. In DNA 2019: International Conference on DNA Computing and Molecular Programming, pages 219-235, 2019.