Arbitrary Nondeterministic Turing Machines  

The approach described above for Minsky's machine can be applied more generally to directly simulate any desired Turing machine. Thus, rather an encoding a desired program into the language interpreted by Minsky's machine, one might choose a more direct approach of creating a Turing machine to directly solve the problem of interest, and translating that machine to a particular custom set of oligonucleotides.

Moreover, it turns out that the same technique can be used to encode arbitrary nondeterministic Turing machines that make random choices in their computations, and explore alternate paths in parallel. The way to do this is simply to include oligos for multiple possible forward transitions from a given head state and tape symbol. Some of the lines of descendants of the initial strand(s) will follow one path, some will follow another. Of course, the total rate of exploration of possible computational paths is limited by the number of template DNA molecules in the reaction vessel. However, this number can feasibly be very large. For example, we estimate that we can produce up to around a 10nM (nanoMolar) concentration of new strands at each step; thus, if we have a PCR machine that can cycle a total of 1 liter of solution, we will be processing around 6*10^15 molecules per step. (This leads to a minor issue of getting rid of old template strands whenever their numbers accumulate to unreasonable levels. This is easily done by, say, periodically diluting the solution and replenishing the other elements of the reaction mixture, or alternatively by periodically filtering out the majority of template strands. Since these steps are more labor-intensive they should be done less often.)