Universal Computation with Watson-Crick D0L Systems.pdf

Universal Computation with Watson-Crick D0LSystemsPetr SoskInstitute of Computer Science, Silesian University, Bezrucovo namest 13, 74601 Opava, Czech Republic, e-mail:petr.sosik@fpf.slu.czTechnical report No. 2000/1AbstractWatson-Crick D0L systems, introduced in 1997 by V. Mihalache andA. Salomaa, arise from two major principles: the Lindenmayer rewritingand the Watson-Crick complementarity principle. Complementarity canbe viewed as a purely language-theoretic operation. Majority of a certaintype of symbols in a string (purines vs. pyrimidines) triggers a transi-tion to the complementary string. The paper deals with an expressivepower of deterministic interactionless Watson-Crick Lindenmayer systems.A rather surprising result is obtained: these systems, consisting of iteratedmorphism and a basic DNA operation, are alone able to express any Turingcomputable function.1 IntroductionSince the time of the Adlemans celebrated experiment [1], a number of theo-retical studies concerning various ideas of universal DNA computing have beenpublished. For an overview see [7] or http://www.wi.leidenuniv.nl/~pier/dna.bib.Nevertheless, the idea of creating a practical synthetic computing system basedon macromolecules still remains elusive due to some unrealistic properties of thesetheoretical models, outrunning the progress in biotechnology. On the other hand,large amount of work was done in study of mathematical foundations of DNAcomputing principles, with results hopefully applicable also in other areas.In this paper we demonstrate the power of the DNA complementarity princi-ple, one of two main sources of the DNA computing power. During the processof rewriting genetic information between DNA and RNA, each symbol of the\natural DNA alphabet A;C;G; T is assigned to its complementary counter-part. In the operational sense, we can describe the complementation principle asa Watson-Crick morphism hW :hW (A) = T; hW (T ) = A hW (C) = G; hW (G) = C:1 The Watson-Crick complementa