Simulating 3-symbol Turing machines with SIMD||DNA

David Doty, Aaron Ong

SIMD||DNA 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 w…