M-State and N-Color (M-N = 1-1, 2-1, and 1-2) Turing Algorithms Demonstrated via DNA Self-Assembly

The fast and extensive generation of patterns using specific algorithms is a major challenge in the field of DNA algorithmic self-assembly. Turing machines (TMs) are simple computable machines that execute certain algorithms using carefully designed logic gates. We investigate Turing algorithms for the generation of patterns on algorithmic lattices using specific logic gates. Logic gates can be implemented into Turing building blocks. We discuss comprehensive methods for designing Turing building blocks to demonstrate an M-state and N-color Turing machine (M-N TM). The M-state and N-color (M-N = 1-1, 2-1, and 1-2) TMs generate Turing patterns that can be fabricated via DNA algorithmic self-assembly. The M-N TMs require two-input and three-output logic gates. We designed the head, tape, and transition rule tiles to demonstrate TMs for the 1-1, 2-1, and 1-2 Turing algorithms. By analyzing the characteristics of the Turing patterns, we classified them into two classes (DL and DR for states grown diagonally to the left and right, respectively) for the 1-1 TM, three for the 2-1 TM, and nine for the 1-2 TM. Among these, six representative Turing patterns generated using rules R11-0 and R11-1 for 1-1 TM, R21-01 and R21-09 for 2-1 TM, and R12-02 and R12-08 for 1-2 TM were constructed with DNA building blocks. Turing patterns on the DNA lattices were visualized by atomic force microscopy. The Turing patterns on the DNA lattices were similar to those simulated patterns. Implementing the Turing algorithms into DNA building blocks, as demonstrated via DNA algorithmic self-assembly, can be extended to a higher order of state and color to generate more complicated patterns, compute arithmetic operations, and solve mathematical functions.