Generation of Diophantine Sets by Computing P Systems with External Output

Generation of Diophantine Sets by Computing P Systems with External Output Álvaro ROMERO JIMÉNEZ and Mario J. PÉREZ JIMÉNEZ Dpto. de Ciencias de la Computación e Inteligencia Articial Universidad de Sevilla, España E-mail: {Alvaro.Romero,Mario.Perez}@cs.us.es Abstract. In this paper a variant of P systems with external output designed to compute functions on natural numbers is presented. These P systems are stable under composition and iteration of functions. We prove that every diophantine set can be generated by such P systems; then, the universality of this model can be deduced from the theorem by Matiyasevich, Robinson, Davis and Putnam in which they establish that every recursively enumerable set is a diophantine set. 1 Introduction In 1998 G. Pun initiated a new branch of the eld of Natural Computing by introducing a new model of molecular computation, based on the structure and functioning of the living cell: transition P systems (see [3]). The framework within which computation are performed in this model is the membrane structure, which recreates the cell-like one. Multisets of symbol-objects are processed along the computations, making them to evolve and distributing them among the membranes. The result of a halting computation is the number of objects collected in a specied output membrane. Since the introduction of this model of computation many variants of it have been proposed. One of them, presented in [5] by G. Pun, G. Rozenberg and A. Salomaa, is the model of transition P systems with external output . In this model, the result of a halting computation is not collected in a xed membrane of the membrane structure, but in the external environment associated with it. In this way, the output of a computation can be thought as a set of strings, instead of as a natural number, as occurred in the basic model. P systems are usually considered as devices which generate numbers. Nevertheless, besides generating devices, they can also be thought as recognizing devices and as computing devices. These kind of P systems have been studied in [6]. In this paper we work with computing P systems, but instead of the basic transition ones we consider those with external output. Thanks to the special functioning of these apparatus, we have been able to dene, in a comfortable manner, several operations between computing P systems with external output; more specically, we have dened composition and iteration, what have allowed us to prove the universality of these devices through the generation of all the diophantine sets. 2 Multisets. Membrane structures. Evolution rules A multiset over a set, A , is an application m:A→IN . A multiset is said to be empty (resp. nite) if its support, supp(m) = {a∈A:m(a)>0} , is empty (resp. nite). If m is a nite multiset over A , we will denote it m={{a1, . . . , ak}} , where the elements ai are possibly repeated. We write M(A) for the set of all the multisets over A . The set of membrane structures , MS , is dened by recursion as follows: 1. [ ] ∈MS ; 2. If µ1, . . . , µn∈MS , then [µ1. . . µn]∈MS . A membrane structure, µ , can also be seen as a rooted tree, V(µ), E(µ) . Then, the nodes of this tree are called membranes , the root node the skin membrane and the leaves elementary membranes of the membrane structure. The degree of a membrane structure is the number of membranes in it. The concepts of depth of a membrane structure and depth of its membranes are easily dened from those of a tree and its nodes. We will also need the notion of level of a membrane within a membrane structure, which is dened as the dierence between the depth of the second and the depth of the rst. The membrane structure with external environment associated with a membrane structure, µ , is µE= [Eµ]E . If we consider the latter as a rooted tree, the root node is called the external environment of µ . Given an alphabet, Γ , we associate with every membrane of a membrane structure a nite multiset of elements of Γ , which are called the objects of the membrane. We also associate with every one of these membranes a nite set of evolution rules . A evolution rule over Γ is a pair (u, v) , usually written u→v , where u is a string over Γ and v=v0 or v=v0δ , where v0 is a string over Γ×{here, out}∪{inl:l∈V(µ)} The idea behind a rule is that the objects in u evolve into the objects in v0 , moving or not to another membrane and possibly dissolving the original one. 3 Computing P systems with external output We are now prepared to introduce our new model of computation. Denition 3.1. A computing P system with external output of order (m, n) and degree p is a tuple Π=Σ, Λ, Γ, #, µΠ, ι, M1, . . . , Mp,(R1, ρ1), . . . , (Rp, ρp) where  Σ is an ordered alphabet of size m , the input alphabet.  Λ is an ordered alphabet of size n , the output alphabet.  Γ is an alphabet such that Σ∪Λ⊂Γ , the working alphabet.  # is a distinguished element in Γ\Σ∪Λ) , the halting element.  µΠ is a membrane structure of degree p , whose membranes we suppose labeled from 1 to p .  The input membrane of Π is labeled by ι∈ {1, . . . , p} .  Mi is a multiset over Γ\Σ associated with the membrane labeled by i , for every i= 1, . . . , p .  Ri is a nite set of evolution rules over Γ associated with the membrane labeled by i , and ρi is a strict partial order over it, for every i= 1, . . . , p . To formalize the semantics of this model we dene rst what a conguration of a P system is, from what follows the notion of computation. Denition 3.2. Let Π be a computing P system with external output.  A conguration of Π is a pair (µE, M) , where µ is a membrane structure such that V(µ)⊆V(µΠ) and has the same root than µΠ , and M is an application from V(µE) into M(Γ) . For every node nd ∈V(µE) we denote Mnd =M(nd) .  Suppose that Π is of order (m, n) and Σ= (a1, . . . , am) . Then, any m -tuple of natural numbers can be codied by a multiset over Σ and given as input to the P system. Thus, the initial conguration of Π for a tuple (k1, . . . , km)∈ INm is the pair (µE, M) , where µ=µΠ , ME=∅ , Mι=Mι∪{{ak1 1. . . akm m}} and Mi=Mi , for every i6=ι . We can pass, in a non-deterministic manner, from one conguration of Π to another by applying to its multisets the evolution rules associated with their corresponding membranes. This is done as follows: given a rule u→v of a membrane i , the objects in u are removed from Mi ; then, for every (ob, out)∈v an object ob is put into the multiset associated with the parent membrane (or the external environment if i is the skin membrane); for every (ob, here)∈v an object ob is added to Mi ; for every (ob, inj)∈v an object ob is added to Mj (if j is not a children membrane of i , the rule cannot be applied). Finally, if δ∈v , then the membrane i is dissolved, that is, it is removed from the membrane structure (the objects associated with this membranes are collected by the parent membrane, and the rules are lost. The skin membrane cannot dissolve). Moreover, the priority relation among the rules forbids the application of a rule if another one of higher priority is applied. Given two congurations, C and C0 , of Π , we say that C0 is obtained from C in one transition step, and we write C⇒C0 , if we can pass from the rst to the second by using the evolutions rules appearing in the membrane structure of C in a parallel and maximal way, and for all the membranes at the same time. Denition 3.3. Given a computing P system with external output of order (m, n) , Π , a computation of Π with input (k1, . . . , km)∈INm is a sequence, possibly innite, of congurations of Π , C0⇒C1⇒. . . ⇒Cq , q≥0 , such that  C0 is the initial conguration of Π for (k1, . . . , km) .  Each Ci is obtained from the previous conguration by one transition step. We say that a computation, C , is a halting computation of Π , if q∈IN and there is no rule applicable to the objects present in its last conguration. Then, the output of a halting computation and of a computing P system with external output can be dened in a natural way. Denition 3.4. Let Π be a computing P system with external output of order (m, n) and suppose that Λ= (b1, . . . , bn) . Let C be a halting computation of Π with input (k1, . . . , km)∈INm and (µE, M) its last conguration. Then, the output of that computation is given by Output(C) = ME(b1), . . . , ME(bn). Denition 3.5. Let Π be a computing P system with external output of order (m, n) . The output of Π with input (k1, . . . , km)∈INm is given by Output(Π;k1, . . . , km) = {Output(C) : C is a halting computation of Π with input (k1, . . . , km)}. The idea behind P systems with external output is that we cannot know what is happening inside the membrane structure, but we can only collect the information thrown from it to the external environment. In accordance with it, it seems natural that the halting computations of these P systems report to the outside when they have reached their nal congurations. Furthermore, the idea behind computing P systems is to use them as computing models of functions between natural numbers. These considerations lead us to the following notions: Denition 3.6. A computing P system with external output of order (m, n) , Π , is said to be valid when the following is veried:  If C is a halting computation of Π , then a rule of the form u→v(#, out) must have been applied in the skin membrane of µΠ , and only in the last step of the computation.  If C is not a halting computation of Π , then no rule of the previous form is applied in the skin membrane in any step of the computation.  For every (k1, . . . , km)∈INm and for every two halting computations, C1 and C2 , of Π with input (k1, . . . , km) , Output(C1) = Output(C2) . Denition 3.7. A computing P system with external output of order (m, n) , Π , computes a partial function, f: INm− → INn , if  Π is a valid P system.  For every (k1, . . . , km)∈INm •f is dened over (k1, . . . , km) if and only if there exists a halting computation of Π with input (k1, . . . , km) . • If C is a halting computation of Π with input (k1, . . . , km) , then Output(C) = f(k1, . . . , km) . We denote CEPm,n p(α, β, γ) , where m, n ∈IN, p ≥1 , α∈ {Pri, nPri} , β∈ {Coo, Cat, nCoo} and γ∈ {δ, nδ} , the family of functions computed by computing P systems with external output of order (m, n) , of degree at most p , and with or without priority, with cooperation, only catalysts or without cooperation (see [3]), and with or without dissolution, respectively. The union, for all p≥1 , of the families of one of these types is denoted CEPm,n(α, β, γ) . 4 Composition of computing P systems with external output We introduce now the operation of composition between computing P systems with external output. Denition 4.1. Let f: INm− → INn and g1: INr− → INs1, . . . , gt: INr− → INst such that s1+· · ·+st=m . Then, the composition of f with g1 to gt , denoted C(f;g1, . . . , gt) , is a partial function from INr to INn dened as follows C(f;g1, . . . , gt)(k1, . . . , kr) = f(g1(k1, . . . , kr), . . . , gt(k1, . . . , kr)) Theorem 4.2. Let f∈CEPm,n(α, β, γ), g1∈CEP r,s1(α, β, γ), . . . , gt∈ CEPr,st(α, β, γ) , with α∈ {Pri, nPri} , β∈ {Coo, Cat, nCoo} and γ∈ {δ, nδ} . Then, C(f;g1, . . . , gt)∈CEPr,n(P ri, Coo, γ) . Proof. Let Πf=Σf, Λf, Γf,#f, µΠf, ιf,Mf 1, . . . , Mf pf,(Rf 1, ρf 1), . . . , (Rf pf, ρf pf) Πg1=Σg1, Λg1, Γg1,#g1, µΠg1, ιg1,Mg1 1, . . . , Mg1 pg1,(Rg1 1, ρg1 1), . . . , (Rg1 pg1, ρg1 pg1) . . . Πgt=Σgt, Λgt, Γgt,#gt, µΠgt, ιgt,Mgt 1, . . . , Mgt pgt,(Rgt 1, ρgt 1), . . . , (Rgt pgt, ρgt pgt) be computing P systems with external output that compute, respectively, the function f and the functions g1 to gt . By means of a renaming of the elements of the alphabets (and, therefore, also of the rules), we can suppose that  Σg1=· · · =Σgt= (a1, . . . , ar) .  Λg1= (b1, . . . , bs1), . . . , Λgt= (bs1+···+st−1+1, . . . , bm) .  Σf= (c1, . . . , cm) .  Λf= (d1, . . . , dn) .  Λg1∪ · · · ∪ Λgt∩Γf=∅ .  #gi6= #gj , for every i6=j . Let us consider the computing P system with external output Π=Σ, Λ, Γ, #, µΠ, ι, M1, . . . , Mp,(R1, ρ1), . . . , (Rp, ρp) given by  Σ= (e1, . . . , er) . (We suppose that Σ∩St i=1 Γgi=∅ ).  There exist distinguished elements ⊕,, ∈ Γ\(Γf∪St i=1 Γgi) .  Λ= (d1, . . . , dn) .  #6= #gi , for every i= 1, . . . , t , and #6= #f .  µΠ= [1µΠg1. . . µΠgtµΠf]1 , where the membranes from µΠg1, . . . , µΠgt, µΠf have been adequately renamed (and therefore, also the rules of the corresponding P systems have been adapted). We denote σg1, . . . , σgt, σf the skin membranes of the latter. Also, we consider that ιg1, . . . , ιgt, ιf reect the new labeling of the input membranes of Πg1, . . . , Πgt, Πf , respectively.  ι= 1 .  p=pg1+· · · +pgt+pf+ 1 .  M1={{#,}} . The remaining multisets are all empty.  The evolution rules are the following: • Evolution rules for membrane 1: ei→(ei, inσg1). . . (ei, inσgt) (i= 1, . . . , r)  → (, inσg1). . . (, inσgt) #g1. . . #gt#→(, inσf)>#→#> bi→(bi, inσf) (i= 1, . . . , m) di→(di, out) (i= 1, . . . , n) #f→(#, out) • For every function fun =g1, . . . , gt, f and for every membrane j of µΠfun , the following rules are included:  → ⊕(, inj1). . . (, injk) u⊕ → Mfun j>⊕ → ⊕ evolution rules associated with the membrane in Πfun where j1 to jk are the children membranes of membrane j and u is its level within µΠfun . Moreover, if j is ιfun , then the rule ⊕ → ⊕ has higher priority than the original rules of Πfun for this membrane. • Let fun be as above and let j1, . . . , jq be the membrane path from σfun to ιfun . Then, for k= 1, . . . , q −1 the following rules are included in membrane jk : ei→(ei, injk+1 ) (i= 1, . . . , r) for fun =g1, . . . , gt bi→(bi, injk+1 ) (i= 1, . . . , m) for fun =f Also, the following rules are included in membrane jq=ιfun . ei→ai(i= 1, . . . , r) for fun =g1, . . . , gt bi→ci(i= 1, . . . , m) for fun =f The P system constructed in this way, denoted C(Πf;Πg1, . . . , Πgt) , is a valid computing P system with external output which computes the composition of f with g1 to gt . Furthermore, it preserves the use or not of dissolution from the P systems which compute the functions. Indeed, the system works as follows:  Phase 1: Computation of the functions g1 to gt over the input data To perform this stage, we need to carry out two operations: the rst one consists of taking the input arguments from membrane 1, which recall is the input membrane of Π , to all the input membranes of the P systems Πg1 to Πgt . This is easily done by displacing the objects representing the arguments through all the necessary membranes. The second operation is a little bit more complicated: in order for a specic P system Πgj to compute correctly the value of the function gj over the input data, we need that all the membranes of this P system start to apply their original rules at the same time (that is, we have to synchronize locally the membranes of each Πgj ). We achieve this by using counters for every one of these membranes. First, we use the object  to activate the counters, represented by objects ⊕ , in all the membranes. These latter objects use objects  to count and, when a certain quantity is reached, the corresponding membrane is allowed to use the rules of Πgj . Because of the way we have implemented this, these quantities turn out to be the levels of the membranes in the structure µΠgj . It is also important that when the P system Πgj starts to compute the value, the objects representing the input data have reached its input membrane. However, as we perform the two operations above simultaneously, we get it for free. Finally, we have to wait until all the values from Πg1 to Πgt have been computed, before allowing the P system Πf to be used (that is, there must be a global synchronization in the skin of Π ). Let us see with greater detail the rules involved in this phase: 1. At the rst step of a computation of Π with input (k1, . . . , kr) , we have in membrane 1 the multiset {{ek1 1, . . . , ekr r,#,}} and the other membranes are empty. Therefore, only the rules which send the objects ei and the object  into the skins of µΠg1 to µΠgt and the rule #→# in membrane 1 can be applied. 2. Now, membrane 1 waits for the values of g1 to gt over (k1, . . . , kr) by means of the rule #→# . With regard to membrane structures µΠg1 to µΠgt , the rule  → ⊕(, inj1). . . (, injk) makes the object  to spread to all their membranes, because when it reaches a particular membrane, it is immediately transformed into a counter object ⊕ and also sent to the children membranes. Thus, from a step of the computation to the next one,  reaches the membranes one depth greater. Meanwhile, the rule ⊕ → ⊕ makes the object ⊕ to generate objects  . A close look to the situation created shows that the activating object  have reached all the membranes exactly when the counter objects ⊕ have generated in each membrane a number of objects  equal to their levels in µΠfun ( fun =g1, . . . , gt ). At that moment, the rule u⊕ → Mfun j introduces in membrane j the objects associated with it in Πfun , and this is done for all the membranes of each Πfun at the same time. From now on, the values of g1 to gt over (k1, . . . , kr) are computed exactly in the same way than the P systems Πg1 to Πgt would do it. 3. Simultaneously, the objects ei cover the path from the skin membrane of each µΠgj to the input membrane of Πgj , by means of the rules ei→ (ei, injk+1 ) , and are changed there into the corresponding objects ai , by means of the rules ei→ai . Note that the objects ei and the object  reach the input membrane at the same time. So, when Πgj starts its original functioning, as stated above, the input data is in its place.  Phase 2: Computation of the function f Phase 1 ends when membrane 1 has collected at least one object of each #g1 to #gt . It is then when the values computed have to be sent as input data to the P system Πf . To synchronize the end of phase 1 with the beginning of phase 2, membrane 1 apply once and again the rule #→# until the rule #g1. . . #gt#→(, inσf) can be used. This latter rule sends an object  into the skin of µΠf , in order to initiate its membranes' counters so that they start to apply their original rules at the same time (local synchronization within Πf ). This is done just as before. Also, in the next step of the computation the objects bi , which represent the values obtained in phase 1, are put into the skin of µΠf and, subsequently, moved, by means of the rules bi→(bi, injk+1 ) , through all the membranes from this one to the input membrane of Πf . Next, the rules bi→ci change them into the corresponding input objects of Πf . It is easy to see that, although there is a gap of one step of computation between when  gets into a membrane and when the bi s do so, this is not at all a problem. Now, the value of the function f over the arguments represented by the objects ci is computed, and along this computation objects di representing the result are thrown out of µΠf . These objects are collected in membrane 1, and immediately expelled from µΠ . The calculation nishes when some objects #f are collected in membrane 1 and they are expelled from µΠ as objects # . ut 5 Iteration of computing P systems with External Output We introduce now the operation of iterating a computing P system with external output. Denition 5.1. Let f: INm− → INm . Then, the iteration function of f , denoted It(f) , is a partial function from INm+1 to INm dened as follows: It(f)(x,0) = x It(f)(x, n + 1) = It(f)(f(x), n) Theorem 5.2. Let f∈CEPm,m(α, β, nδ) , with α∈ {Pri, nPri} and β∈ {Coo, Cat, nCoo} . Then It(f)∈CEP m+1,m(Pri, Coo, nδ) . Proof. Let Πf=Σf, Λf, Γf,#f, µΠf, ιf,Mf 1, . . . , Mf pf,(Rf 1, ρf 1), . . . , (Rf pf, ρf pf) be a computing P system with external output such that computes f . By means of a renaming of the elements of the alphabets (and, therefore, also of the rules), we can suppose that  Σf= (a1, . . . , am) .  Λf= (b1, . . . , bm) . Let us consider the computing P system with external output Π=Σ, Λ, Γ, #, µΠ, ι, M1, . . . , Mp,(R1, ρ1), . . . , (Rp, ρp)) verifying the following  Σ= (c1, . . . , cm+1) , and is such that Σ∩Γf=∅ .  There exist distinguished elements ⊕,,,⊗, ∈ Γ\Γf .  Λ= (c1, . . . , cm) .  #6= #f .  µΠ= [1µΠf]1 , where the membranes from µΠf have been adequately renamed (and therefore, also the rules of Πf have been adapted). We denote σf the skin membrane of the latter. Also, we consider that ιf reects the new labeling of the input membrane of Πf .  ι= 1 .  p=pf+ 1 .  M1={{#}} . The remaining membranes are all empty.  The evolution rules are the following: • Evolution rules for membrane 1: #cm+1 →(, inσf)>#ci→#(ci, out) (i= 1, . . . , m)> >#→(#, out)>#f#f→#f>#f→(, inσf)> >⊗ubi→ ⊗uci(i= 1, . . . , m)>⊗u→#> > ci→(ci, inσf) (i= 1, . . . , m) where u is the degree of µΠf .