Universal computation with Watson-Crick D0L systems

Watson-Crick D0L 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.