On the universality of Post and splicing systems

AbstractIn search for a universal splicing system, in this paper we present a Post system universal for the class of Post systems, and we discuss its translation into an extended splicing system with multiplicity. We also discuss the complexity of the resulting universal splicing system, comparing our result with recent known results about the translation of universal Turing machines into splicing systems