Universal Systems with Operations Related to Splicing

Abstract

Following some of the most recently obtained results on the computational universality of specific variants of H systems (e.g. see [6, 9, 13] we introduce systems based on new operations that are closely related to the splicing operation, i.e. we consider the operations of cutting a string at a specific site into two pieces with marking them at the cut ends and of recombining two strings with specifically marked endings. Whereas in the splicing of two strings these strings are cut at specific sites and the cut pieces are recombined immediately in a crosswise way, in the CR (cutting/recombination) systems introduced in this paper cutting can happen independently from recombining the cut pieces. Nevertheless, we shall show how a Turing machine computing a partial recursive function can be simulated by an equivalent mCR system (i.e. a CR system working in the multiset style, where the numbers of copies of all available strings are counted) with a finite set of cutting/recombination rules as well as with a finite set of axioms; in that way, from a universal Turing machine we obtain a universal mCR system.