DNA computers in vitro and vivo

We show how DNA molecules and standard lab techniques may be used to create a nondeterministic Turing machine. This is the first scheme that shows how to make a universal computer with DNA. We claim that both our scheme and previous ones will work, but they probably cannot be scaled up to be of practical computational importance. In vivo, many of the limitations on our and previous computers are much less severe or do not apply. Hence, lifeforms ought, at least in principle, to be capable of large Turing universal computations. The second part of our paper is a loose collection of biological phenomena that look computational and mathematical models of computation that look biological. We observe that cells face some daunting computational problems, e.g. gene regulation, assembly of complex structures, and antibody synthesis. We then make simplified mathematical models of certain biochemical processes and investigate the computational power of these models. The view of "biology as a com..