Computation in chemical graph rewriting networks

Abstract Biological systems are frequently viewed as performing computations that are implemented by chemical transformations underlying the turn-over of their molecular components. In chemical reaction networks, computation may refer to at least two fundamentally different aspects: concentrations of molecules, and molecular structures. The latter can be captured by modeling chemical reactions as a rewriting system acting on structural formulae, i.e. labeled graphs. We investigate the computational power of double-pushout (DPO) graph rewriting restricted to chemical graphs and show that chemical graph rewriting is sufficient to emulate Turing machines and two-tag systems on polymeric graphs that act as tapes. Moreover, we raise the question whether chemistry, modeled as DPO graph rewriting together with some additional form of chemical programs, may be computationally universal in the strong sense, i.e. capable of computing any computable function on chemical graphs.