DNA computing based on splicing: universality results

Abstract. The paper extends some of the most recently obtained results on the computational universality of speci c variants of H systems (e. g. with regular sets of rules) and proves that we can construct universal computers based on various types of H systems with a nite set of splicing rules as well as a nite set of axioms, i. e. we show the theoretical possibility to design programmable universal DNA computers based on the splicing operation. For H systems working in the multiset style (where the numbers of copies of all available strings are counted) we elaborate how aTuring machine computing a partial recursive function can be simulated by an equivalent H system computing the same function � in that way, from a universal Turing machine we obtain a universal H system. Considering H systems as language generating devices we have to add various simple control mechanisms (checking the presence/absence of certain symbols in the spliced strings) to systems with a nite set of splicing rules as well as with a nite set of axioms in order to obtain the full computational power, i. e. to get a characterization of the family of recursively enumerable languages. We also introduce test tube systems, where several H systems work in paralle