Universal computation with Watson-Crick DOL systems
Watson-Crick DOL systems, introduced in 1997 by Mihalache and Salomaa, arise from two major principles: the Lindenmayer rewriting and the Watson-Crick complementarity principle. Complementarity can be viewed as a purely language-theoretic operation. Majority of a certain type of symbols in a string (purines vs. pyrimidines) triggers a transition to the complementary string. The paper deals with an expressive power of deterministic interactionless Watson-Crick Lindenmayer systems. A rather surprising result is obtained: these systems, consisting of iterated morphism and a basic DNA operation, are able to compute any Turing computable function. (C) 2002 Elsevier Science B.V. All rights reserved.
watson-crick complementarity lindenmayer system dna computing