Turing, Watson-Crick and Lindenmayer. Aspects of DNA Complementarity

摘要

Watson-Crick complementarity is one of the very central components of DNA computing, the other central component being the massive parallelism of DNA strands. While the latter component drastically reduces time complexity, the former component is the cause behind the Turing universality of models of DNA computing. This paper makes this cause explicit and also discusses it in terms of some specific models. Finally, another aspect of complementarity, the operational one, will be discussed in terms of Lindenmayer systems.