T.Yokomori, S.Kobayashi, C.Ferretti
On the power of circular splicing systems and DNA computability.
Abstract
A new type of generative mechanisms was recently introduced undet the name of
extended H systems, and it has been shown that extended H systems with finite
sets of axioms and finite sets of rules exactly characterize the recursively
enumerable languages, thus having the full power of Turing machines. Also, it
was shown that there is a universal extended H system analogous to a universal
Turing machine.
In this paper, we propose a new type of splicing models called circular H
system, and show that they have the same computational power as Turing
machines. Proposed new models are based on circular splicings which come from
biological motivations of interactions between linear and circular DNA
sequences, and hence, the models seem to have some advantages over other
existing models dealing with only linear strings.
We also show that there effectively exists a universal circular H system which
can simulate any circular H system with the same terminal alphabet, which
naturally leads us to a feasible design for DNA computer based on circular
splicing.
Surprizingly, all these results are obtained without considering multiplicity
constraints, which is in marked contrast to the previous results for linear H
systems.