Extracting Computational Results from Solution  

Once we have run a deterministic or nondeterministic DNA computation for a sufficient number of cycles that we think some molecules might have had time to reach successful final configurations, how do we then find out the result of the computation? This is done easily enough, as follows.

First, we design the machine such that upon reaching a successful final state, it records a distictive base-sequence on the tape indicating success, and then executes a series of transitions that are difficult to reverse. One way to do this might be to take advantage of the energy asymmetry of complementary pairs of mismatched bases. For example, pairing a C in an oligo with an A on a template is less likely than the complementary event, pairing a T on an oligo with a G on a template. Thus it seems possible to design a limited series of base-changes that is more likely to go forwards than backwards.

A simpler irreversible transition is simply to have the reaching of the final state trigger a rewrite rule that erases the tape head in one fast step, using a special long oligo that can tolerate a larger number of mismatches than normal, and whose action can thus not be reversed by any other oligo in the solution. With no tape head, the tape contents (ignoring the movements of any history particles) cannot change. Thus, molecules that have reached successful final states will "breed true," and, over time, their identical descendants will come to dominate the mixture of template molecules.

In either case, once we have done a sufficient number of steps so that we expect there to be detectable quantities of molecules expressing the desired result, we select for those molecules containing the distictive "success" sequence recorded on them, via using any of a number of known molecular biology techniques such as filter hybridization, radioactive probes, etc. We take the resulting molecules and sequence them. If the molecules are not identical, such as will be the case if we are solving a nondeterministic machine with multiple valid solutions or if we are using history particles to speed up forward progress, then direct sequencing will not work; an alternative might be to first dilute the solution down to a single (expected) molecule, and amplify that using clean PCR (with no mutagenic oligos), and then sequence the resulting population of identical molecules. This dilution-amplification technique is reportedly unreliable, but it can simply be repeated until it works.

Thus, we can perform arbitrary nondeterministic computations in an astronomically parallel way, using simple repeated PCR cycles with little intervention other than occasional thinning of the template strand population and replensishing of reactants. At any desired time, we can easily query the reaction mixture to see if any of the trillions of molecules has stubled upon a solution to the given problem yet, and if so, we can read that result out. We believe this discovery to be a result of major potential significance for solving very large and difficult NP-hard search problems. The degree of parallism can be easily scaled up by simply having more copies of the reaction mixture running simultaneously on more machines. If a solution is not found quickly, the computation can simply be continued for as long as is necessary until a result is found. The expected time to find a solution is roughly inversely proportional to the number of liters of mixture that are being run, except that there is a lower bound, which is the time required for a line of descendants to proceed immediately to the desired solution down the most direct path.