One and Two Polarizations, Membrane Creation and Objects Complexity in P Systems
Abstract
We improve, by using register machines, some existing universality results for specific models of P systems. P systems with membrane creation are known to generate all recursively enumerable sets of vectors of non-negative integers, even when no region (except the environment) contains more than one object of the same kind. We here show that they generate all recursively enumerable languages, and two membrane labels are sufficient (the same result holds for accepting all recursively enumerable vectors of non-negative integers). Moreover, at most two objects are present inside the system at any time in the generative case. Then we prove that 10 + m symbols are enough to generate any recursively enumerable language over m symbols. P systems with active membranes without polarizations are known to generate all recursively enumerable sets of vectors of non-negative integers. We show that they generate all recursively enumerable languages; four starting membranes with three labels or seven starting membranes with two labels are sufficient. P systems with active membranes and two polarizations are known to generate/accept all recursively enumerable sets of vectors of non-negative integers, only using rules of rewriting and sending objects out. We show that accepting can be done by deterministic systems. Finally, remarks and open questions are presented.
Full text
One and Two Polarizations, Membrane Creation and Objects Complexity in P Systems Artiom Alhazov1,2, Rudolf Freund3and Agust´ ın Riscos-N´ u˜ nez4 1Research Group on Mathematical Linguistics, Rovira i Virgili University Pl. Imperial T` arraco 1, 43005 Tarragona, Spain E-mail: artiome.alhazo[email protected].es 2Institute of Mathematics and Computer Science, Academy of Sciences of Moldova Str. Academiei 5, Chis¸in˘ au, MD 2028, Moldova E-mail: [email protected] 3Faculty of Informatics, Vienna University of Technology Favoritenstr. 9, A–1040 Vienna, Austria E-mail: [email protected] 4Research Group on Natural Computing Department of Computer Science and Artificial Intelligence, University of Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain E-mail: [email protected] Abstract We improve, by using register machines, some existing universality results for specific models of P systems. P systems with membrane creation are known to generate all recursively enumerable sets of vectors of non-negative integers, even when no region (except the environment) contains more than one object of the same kind. We here show that they generate all recursively enumerable languages, and two membrane labels are sufficient (the same result holds for accepting all recursively enumerable vectors of non-negative integers). Moreover, at most two objects are present inside the system at any time in the generative case. Then we prove that 10 + msymbols are enough to generate any recursively enumerable language over msymbols. P systems with active membranes without polarizations are known to generate all recursively enumerable sets of vectors of non-negative integers. We show that they generate all recursively enumerable languages;four starting membranes with three labels or seven starting membranes with two labels are sufficient. P systems with active membranes and two polarizations are known to generate/accept all recursively enumerable sets of vectors of non-negative integers, only using rules of rewriting and sending objects out. We show that accepting can be done by deterministic systems. Finally, remarks and open questions are presented. 1. Introduction P systems with symbol objects are a theoretical framework of distributed parallel multiset processing, launched by Gh. P˘ aun in 1998 ([6]). A systematic field survey can be found in [7]; [9] contains a comprehensive bibliography. The aim of this article is to improve descriptive complexity parameters or properties of a few universality results. More precisely, we shall speak about object complexity (bounds in the starting configuration, in any configuration, in the alphabet) and also about membrane complexity. Let us denote the set of all recursively enumerable sets of (k-dimensional) vectors of non-negative integers by PsRE (PsRE(k),respectively), while the set of all recursively enumerable languages (over a k-letter alphabet) is denoted by RE (RE (k),respectively). It was shown in [1] that P systems with membrane creation generate PsRE, even when every region (except the environment) contains at most one object of every kind, but using an unbounded number of membrane labels. We will show that RE is generated using only two membrane labels and at most two objects present inside the system throughout any computation. The accepting case is considered, too, and again two membrane labels are enough. On the
other hand, using an unbounded membrane alphabet we can bound the symbol alphabet by 10 + mobjects, where mis the size of the output alphabet. We also know from [1] that P systems with active membranes without polarization generate PsRE, again working with an unbounded number of membranes. We will show that RE is generated by P systems with four membranes and three labels or seven membranes with two labels in the initial configuration. As shown in [2, 3], P systems with two polarizations and rules of types (a)– rewriting – and (c)– sending an object out – generate PsRE using two membranes or accept PsRE using one membrane. In this article we will show that deterministic systems of this kind with one membrane accept PsRE. 2. Definitions After some preliminary definitions, we recall basic facts of register machines and matrix grammars (without appearance checking) and give the necessary definitions for the specific models of P systems considered in this paper. 2.1. Preliminaries The set of non-negative integers is denoted by N.An alphabet Vis a finite non-empty set of abstract symbols. Given V, the free monoid generated by Vunder the operation of concatenation is denoted by V∗;theempty string is denoted by λ, and V∗−{λ}is denoted by V+.By|x|we denote the length of the string xover V. For more notions as well as basic results from the theory of formal languages, the reader is referred to [4] and [8]. 2.2. Register machines Aregister machine is a construct M=(m, P, l0,l h), where mis the number of registers, Pis a finite set of instructions injectively labelled with elements from a given set lab(M),l0is the initial/start label, lhis the final label. The instructions are of the following forms: –l:(A(r),l,l) Add 1to the contents of register rand proceed to the instruction (labelled with) lor l (ADD instruction). For deterministic machines, we require l=l . –l:(S(r),l,l) If register ris not empty, then subtract 1from its contents and go to instruction l, otherwise proceed to instruction l (conditional SUB instruction). –lh:halt Stop the machine. When considering the generation of languages, we use the model of a register machine with output tape, which also uses a tape operation: –l:(write(a),l) Write symbol aon the output tape and go to l. We then also specify the output alphabet Tin the description of the register machine with output tape, i.e., we write M=(m, T, P, l0,l h). The following results are folklore (e.g., see [5]): Proposition 1 Let L⊆Nmbe a recursively enumerable set of (vectors of) non-negative integers. Then Lcan be generated/accepted by a register machine/deterministic register machine with at most m+2registers; moreover, at the beginning/at the end of a computation, all registers are empty; the result/the input of a computation appears in the first m registers. Let L⊆V∗be a recursively enumerable language. Then Lcan be generated by a register machine with output tape with 2registers. 2.3. Matrix grammars A context-free matrix grammar (without appearance checking) is a construct G=(N,T,S,M)where Nand T are sets of non-terminal and terminal symbols, respectively, with N∩T=∅,S∈Nis the start symbol,Mis a finite set of matrices,M={mi|1≤i≤n}, where the matrices miare sequences of the form mi=(mi,1,···,m i,ni), ni≥1,1≤i≤n, and the mi,j,1≤j≤ni,1≤i≤n, are context-free productions over (N,T). For mi=(mi,1,···,m i,ni)and v,w ∈(N∪T)∗we define v=⇒miwif and only if there are w0,w 1,···,w ni∈ (N∪T)∗such that w0=v, wni=w, and for each j, 1≤j≤ni,wjis the result of the application of mi,j to wj−1. The language generated by Gis L(G)={w∈T∗|S=⇒mi1w1···=⇒mikwk=w, wj∈(N∪T)∗,m ij∈Mfor 1 ≤j≤k, k ≥1}. The family of languages generated by matrix grammars without appearance checking is denoted by MATλ.Itis known that for the family of Parikh sets of languages generated by matrix grammars PsMATλwe have PsMATλ⊂ PsRE. Further details about matrix grammars can be found in [4] and in [8]. We only mention that the power of matrix grammars is not decreased if we only work with matrix grammars in the f-binary normal form where Nis the disjoint union of N1,N 2,and {S, f}, and Mcontains rules of the following forms: 1. (S→XA),with X∈N1,A∈N2;
2. (X→Y,A →x),with X∈N1,Y ∈N1∪{f}, A∈N2,and x∈(N2∪T)∗,|x|≤2; 3. (f→λ). Moreover, there is only one matrix of type 1 and only one matrix of type 3, which is only used in the last step of a derivation yielding a terminal result. 2.4. P Systems The first model of P systems we consider is that of Psystems with non-cooperative multiset-rewriting rules (ncoo) with specifying targets (tar), also using membrane creation (mcre) and membrane dissolution (δ) possibilities. Such a system (of initial degree m≥1)isoftheform Π=(O,H, μ,w1,···,w m,R 1,···,R n) where Ois the alphabet of objects, His the set of labels for membranes (we assume here that Hcontains nlabels), μis the initial membrane structure, consisting of mmembranes labelled (not necessarily in a one-to-one manner) with elements of H,w1,···,w mare strings over Orepresenting the multisets of objects present in the mcompartments (also called regions) of μ, and R1,···,R nare the (finite) sets of rules associated with the nlabels from H. These rules can be of the forms (1) a→vand (2) a→[ib]iwhere v∈O∗,a, b ∈O,i∈H, and either v∈(O×tar)∗or v∈(O×tar)∗{δ}, with tar ={here, out}∪{inj|j∈H}. The presence of δ on the right-hand side of a rule means that the application of the rule leads to the dissolution of the membrane. The meaning of a rule of type (1) is that the object a from the region associated with the rule “reacts”, and as a result the objects specified by vare produced. The objects from vhave associated target commands,oftheformshere, out,inj, which specify where the object should be placed: here means that the object remains in the region where it is produced, injmeans that it has to go to the membrane j, provided that it is directly inside the membrane where the rule is applied (otherwise the rule cannot be used), and out indicates that the object should exit the current membrane, going to the surrounding region – which is the environment in the case of the skin membrane of the system. In general, the indication here is not explicitly written. If the special symbol δis present, this means that after using the rule the membrane is dissolved, and all its contents, objects and membranes alike, become elements of the surrounding region. The skin membrane is never dissolved. A rule a→[ib]iof type (2) means that object aproduces a new membrane, with label i, containing the object b. Knowing the label of the membrane, we also know the rules associated with it. We recall that the number of membrane labels (i.e., kinds of membranes) is n(the rules are associated with the membrane labels), while the number of membranes initially is mand can change during the computation. The rules are used in the non-deterministic (the objects and the rules are chosen non-deterministically) maximally parallel way (no further object can evolve after having chosen the objects for the rules), thus obtaining transitions from one configuration of the system to another one. P systems with active membranes with kpolarizations (activek) are constructs Π=(O,H, E,μ,w1,···,w m,R) where the components O,H,μ,w1,···,w mare defined in the same way as above, the membranes of μalso have associated polarizations from E(having cardinality k), and the rules from Rare of the following forms: (a): [a→v]e h– rewriting-like, (b): a[] e h→[b]e hand (c): [a]e h→[] e hb – bring an object inside the membrane/send an object out of the membrane (possibly changing its polarization), (d): [a]e h→b– dissolve the membrane, producing another object (the contents of the dissolved membrane is released to the surrounding region), (e): [a]e h→[b]e h[c]e h–membrane division, where two membranes with the same label (but possibly different polarizations) are produced, each containing a new object (all other objects are duplicated). In all cases, a, b, c ∈O, v ∈O∗,e, e,e ∈Eand h∈H. The rules of type (a)are applied in the maximally parallel way, while at most one rule of types (b),(c),(d),(e)can be applied for each membrane at any step of the computation. If we have only one polarization, we omit specifying it (and in the literature, the subscript 0then is usually added to the types of rules defined above, thus yielding (a0), etc.). In both models, when a configuration is reached where no rule can be applied, the computation stops, and the multiplicity of objects sent into environment during the computation is said to be computed by the system along that computation. By Ps(Π) we denote the set of vectors generated in this way (by means of all computations) by a system Π. If we take into account the sequence of symbols as they are sent out into the environment (when two or more objects leave the system at the same moment, then all permutations of these objects are considered), then we obtain the string language generated by Π, denoted by L(Π) .When considering Πas an accepting system for a set of vectors, we put the input multiset into the skin membrane and accept by halting computations. We denote the resulting families generated by such P systems by XOn1,n2,n3Pn4,n5,n6Fwhere (1) Xis either Lfor languages or Psfor sets of vectors of non-negative integers; we add the subscript awhen considering accepting systems; (2) Fis the list of features used in the model (e.g., we consider (ncoo, tar, mcre, δ),(active1,a,b,c,d,e), and (active2,a,c)); (3) the numbers n4,n 5,n 6represent the
bounds on the starting number of membranes, the maximal number of membranes in any computation, and the number of membrane labels, ∗representing the absence of a bound (if all three numbers are ∗, then we simply omit them all); (4) the numbers n1,n 2,n 3have the same meaning, but for the objects inside the system; the middle parameter, n2or n5, can be replaced by n 2/n2or n 5/n5where the primed numbers indicate the bounds on the number of objects or membranes ever present in the system during halting computations only, thus refining this complexity measure. 3. Membrane Creation Figure 1 describes the membrane structure used in the first theorems. Th. 1 1 1 2@2 ··· n1 HH2 2@2 ··· n2 Th. 2 1 2 2@2 ··· n1 HH1 2 2@2 ··· n2 ...1 HH12 2@2 ··· nd Th. 3 s @ ··· nonterminals Th. 4,5 s 1 1 ··· n1 @@2 HHHH2 ··· n2 l l Figure 1. Membrane structures for membrane creation proofs Generating The first theorem shows how recursively enumerable languages can be generated by P systems with a small number of objects inside the system and a small number of membrane labels. Theorem 1 LO1,2,∗P1,∗,2(ncoo, tar, mcre, δ)=RE. Proof. Due to Proposition 1, we construct a P system simulating a register machine M=(2,T,P,l 0,l h);P−denotes the set of all SUB instruction labels. Π= O,H, [1]1,w 1,R 1,R 2, O=T∪{a1,a 2,C 1,C 2,g 0,g 1,g 2,t} ∪P∪{l1,l 2,l 3,l 4,l 5,l 6,l 7|l∈P−}, H={1,2}, w1=g0, R1=R1,I ∪R1,A ∪R1,S ∪R1,D ∪R1,Z ∪R1,O, R2=R2,I ∪R2,A ∪R2,S ∪R2,D ∪R2,Z. For clarity, the rules are grouped in categories (initialization, add, subtract, decrement case, zero case, output). Initialization: R1,I ={g0→[2g0]2,g 1→[1g2]1,g 2→(l0)out}, R2,I ={g0→(g1)out}, Output: R1,O ={l→laout |a∈T, l:(write(a),l)∈P}, Add: R1,A ={l→l(C2)ini,l→l (C2)ini |l:(A(i),l,l)∈P, i ∈{1,2}} ∪{C2→[2t]2,t→λ} R2,A ={C2→[2t]2,t→λ}, Subtract: R1,S ={l→(l1C1)ini |l:(S(i),l,l)∈P, i ∈{1,2}}, ∪{C1→[1t]1} ∪{l1→(l2)in2,|l:(S(1),l,l)∈P}, R2,S ={C1→[1t]1} ∪{l1→(l2)in2|l:(S(2),l,l)∈P}, Decrement case: R1,D ={l4→l5δ|l∈P−} ∪{l3→(l4)in1,l 5→(l)out |l:(S(1),l,l ∈P)}, R2,D ={l2→l3δ|l∈P−} ∪{l3→(l4)in1,l 5→(l)out |l:(S(2),l,l ∈P)}, Zero case: R1,Z ={l6→l7δ|l∈P−} ∪{l1→(l6)in1,l 7→(l)out |l:(S(1),l,l ∈P)}, R2,Z ={l1→(l6)in1,l 7→(l)out |l:(S(2),l,l ∈P)}. Initially, by means of the auxiliary objects gi, we create two membranes inside the skin region, labelled by 1and 2, respectively. These membranes will be referred to as cluster-membranes (because they will contain inside them a number of elementary membranes). We finish the initialization phase by generating an object l0in the skin region. The values of the two registers i,i∈{1,2}, are represented by the number of elementary membranes labelled by 2that occur inside the corresponding cluster-membrane i. The duty of the object Ciis to create membrane i. Object tis not needed for the computation, it is only used to keep the usual form of membrane creation rules and immediately erased after having been created. Writing an output symbol a∈Tis done by a noncooperative rule changing the instruction label and producing a symbol athat is immediately sent out. To increment a register, a membrane labelled by 2is created inside the corresponding cluster-membrane. In order to simulate a subtraction on register iwe send the objects l1and C1into the cluster-membrane iand then proceed in the following way: while creating a membrane with label 1, object l1tries to enter in some membrane with label 2as l2. If such a membrane exists (i.e., register iis not empty), then l2changes to l3and dissolves the membrane, thus being spilled back into the cluster-membrane.
Before proceeding to the next label, we have to get rid of the auxiliary membrane 1that was created inside the clustermembrane by C1.Tothisaim,l3enters into membrane 1as l4and dissolves it, thereby changing to l5. Finally, l5sends an object lout to the skin region. As an overall result, l has been replaced by land the number of membranes with label 2inside the cluster-membrane ihas been reduced by 1. If, on the other hand, no membrane with label 2exists in the cluster membrane, then l1waits for one step and then enters the newly created membrane 1as l6. Immediately afterwards, it changes to l7and dissolves the membrane. Finally, l7sends out an object l into the skin region. As an overall result, in the absence of membranes with label 2 inside the cluster-membrane i,lhas been replaced by l. Notice that inside the system there can never be more than one copy of the same object. In fact, the number of objects inside the system never exceeds two (it can only be two after the first step of an ADD or a SUB instruction). Accepting Notice that the simulation of the register machine instructions in Theorem 1 is deterministic (the nondeterminism arises from the non-determinism of the register machine program itself, not from the simulation). For the case of accepting sets of vectors in a deterministic way, we also specify the cardinality of the input alphabet, i.e., the number of components in the (Parikh) vectors. Theorem 2 DPsa(m)OP1,∗,2(ncoo, tar, mcre, δ)= PsRE(m). Proof. Given a recursively enumerable set of vectors of non-negative integers, we now simulate a register machine M=(m+2,P,l 0,l h)(see Proposition 1); the input vector is represented in the skin by the corresponding numbers of symbols (ai,i),1≤i≤m,forthei-th component. Π= O,H, [1]1,w 1,R 1,R 2, O={(ai,j)|1≤i≤m+2,1≤j≤i} ∪{C1,C 2,t}∪{gi|0≤i≤4(m+2)} ∪P∪{l1,l 2,l 3,l 4,l 5,l 6,l 7|l∈P−}, ∪{(l,k, j)|l∈P−, 0≤k≤2,1≤j≤m+2}, H={1,2}, w1=g0, R1=R1,I ∪R1,A ∪R1,S ∪R1,D ∪R1,Z, R2=R2,I ∪R2,A ∪R2,S ∪R2,D ∪R2,Z. Like in the previous theorem, we list the rules by categories (initialization, add, subtract, decrement case, zero case). We again start with the object g0 which now starts the creation of the membrane structure [1[2]2m+2]1m+2 , where each membrane with label 2(cluster membrane) corresponds to a register. In parallel, the input objects enter the corresponding membranes and become membranes with label 2, see Figure 1. Initialization: R1,I ={g3i→[2g3i+1 ]2,g 3i+2 →[1g3i+3 ]1, g3(m+2)+i→g3(m+2)+i+1out |0≤i≤m+1} ∪{g4(m+2) →l0} ∪{(ai,j)→(ai,j−1)in1|1≤i≤m, 2≤j≤i} ∪{(ai,1) →(C2)in2|1≤i≤m}, R2,I ={g3i+1 →(g3i+2)out |0≤i≤m+1} ∪{C2→[2t]2,t→λ}. Then we perform a deterministic simulation of the instructions in the program of the deterministic accepting register machine M. We now list the rules for ADD instructions (registers m+1,m+2for the simulation of the working registers; observe that for the input initialization of the registers i,1≤i≤m, similar rules for the corresponding symbols (ai,i)are used): Add: R1,A ={l→l(ai,i),l→l (ai,i), (ai,j)→(ai,j−1)in1, (ai,1) →(C2)in2|l:(A(i),l,l)∈P, m+1≤i≤m+2,2≤j≤i}, R2,A ={C2→[2t]2,t→λ}. The main reason for additional rules is that we have to go to that level of the membrane structure which corresponds to the register affected by the instruction. The same has to be done for the SUB instructions: Subtract: R1,S ={l→(l,0,i),(l,0,1) →(l1C1)in2 |l:(S(i),l,l)∈P} ∪{(l,0,j)→(l,0,j−1)in1|2≤j≤i, l:(S(i),l,l)∈P} ∪{(l,k, j)→(l, k,j −1)out |2≤j≤i, 1≤k≤2,l:(S(i),l,l )∈P} ∪{(l,1,1) →l,(l,2,1) →l |l:(S(i),l,l)∈P} ∪{t→λ}, R2,S ={l1→(l2)in2,C 1→[1t]1}. The decrement case and the zero case are handled very much like it is done in Theorem 1 for register 2. Decrement case: R1,D ={l4→l5δ|l∈P−} R2,D ={l2→l3δ|l∈P−} ∪{l3→(l4)in1,l 5→(l,1,i)out |l:(S(i),l,l ∈P)}, Zero case: R1,Z ={l6→l7δ|l∈P−}, R2,Z ={l1→(l6)in1,l 7→(l,2,i)out |l:(S(i),l,l ∈P)}.
After the correct simulation of the decrement case or the zero case, the symbol (l, 1,i)or the symbol (l, 2,i),respectively, is released; by decrementing the third component, these symbols can travel along the line of membranes labelled by 1back to the skin membrane, where the rule (l,1,1) →lor the rule (l,2,1) →l is applied; hence, after decrementing, the label lis obtained, whereas in the zero case we continue with label l . We finally observe that all the derivations in Πare performed deterministically, which completes the proof. Generating with one object Considering P systems only having one object inside the system during the whole computation, we realize that such P systems with one object work in a sequential way, hence, the following holds: Theorem 3 PsMATλis characterized by P systems Π=(O,H, μ,w1,···,w m,R 1,···,R n) where (a) the initial membrane structure is limited by two levels (any membrane inside the skin is elementary) and the label 1of the skin membrane is unique (i.e., the labels of the other membranes inside are different from 1), (b) exactly one of the multisets wiconsist of exactly one object, whereas all the other initial multisets are empty, (c) the rules in R1are of the forms a→buout,a→biniuout, a→b,ora→[ib]iwith a, b ∈O,u∈O∗, and i∈H where H=H−{s}, (d) the rules in Ri,2≤i≤n,are of the forms a→b,a→bout,ora→bδ. Proof. Let Πbe a P system obeying to the conditions given above. We first observe that due to the form of the initial configuration as well as due to the restricted forms of the rules, during any computation (i) the membrane structure is limited by two levels (any membrane inside the skin is elementary), (ii) the number of symbols inside the system is exactly one. Therefore, when constructing a matrix grammar G=(N,T,S,M)simulating Π, with T⊆O, a membrane ican be represented by the nonterminal i, while the object aand its position in membrane ican be stored as a pair (a, i). With InCon denoting the set of representations of the initial configuration given by μ, w1,···,w m(in fact only one such representation is necessary), we now can specify the matrix grammar Gas follows: N=H∪O×H∪{ (a, i)|(a, i)∈F}, M={(S→w)|w∈InCon} ∪{((a, s)→(b, s)u)|a→buout ∈Rs} ∪{((a, s)→(b, i)u, i →i)| a→biniuout ∈Rs,i∈H} ∪{((a, i)→(b, i)) |a→b∈Ri,i∈H} ∪{((a, i)→(b, s)) |a→bout ∈Ri,i∈H} ∪((a, s)→(b, i)i)|a→[ib]i∈Rs,i∈H ∪{((a, i)→(b, s),i→λ) |a→bδ ∈Ri,i∈H} ∪{((a, i)→(a, i)),((a, i)→λ)|(a, i)∈F} ∪{ (a, i)→(a, i),j →λ)|(a, i)∈F, i∈H,j∈H} ∪{ (a, s)→(a, s),j →λ)|(a, s)∈F, j∈H−Ha}. The set F⊂O×His defined in such a way that a pair (a, i)is in Fif and only if no rules of region iare applicable to a, eventually except for rules of the form a→binjuout in R1, and for any a∈O,Ha⊂Hdenotes the set of membrane labels jsuch that Rscontains rules of the form a→binjuout,a, b ∈O, u ∈O∗. We now can see that a configuration with object ain region iis a halting one if and only if (a, i)∈Fand (i) either i=sor (ii) i=s and no membranes with labels from Haare present. The rules with the barred symbols (a, i)allow us to remove all non-terminal symbols from the sentential form of Mwhen Πhas reached a halting configuration. Hence, Ps(L(M)) equals the set of vectors generated by Π. For showing the converse inclusion, we consider a matrix grammar G=(N,T,S,M)without appearance checking in the f-binary normal form and construct a P system Π simulating G:Πstarts with the initial configuration [sS]s. Π=(O,H, [s]s,S,R Ainit ,···,R s), O={S, S1,f,#}∪N1 ∪{li|l∈M, 0≤i≤4}, H=N2∪{s}, Rs={S→[Ainit S1]Ainit |(S→XinitAinit)∈M} ∪{X→(l0)inA|l:(X→Y,A →uv)∈M} ∪{l1→[ul2]u |l:(X→Y,A →uv)∈M, u ∈N2} ∪{l1→l3uout |l:(X→Y,A →uv)∈M, u ∈T∪{λ}} ∪{l3→[vl4]v |l:(X→Y,A →uv)∈M, v ∈N2}, ∪{l3→Yv out |l:(X→Y,A →uv)∈M, v ∈T∪{λ}} ∪{X→#,|X∈N1∪{#} ∪{f→#inA|A∈N2}, RA={S1→(Xinit)out |(S→XinitA)∈M} ∪{l0→l1δ|l:(X→Y,A →uv)∈M} ∪{l2→(l3)out |l:(X→Y,B →Av)∈M} ∪{l4→(Y)out |l:(X→Y,B →uA)∈M} ∪{#→#}. The rules S→[Ainit S1]Ainit ∈Rsas well as S1→(Xinit)out ∈RAinit simulate the start matrix by producing a membrane corresponding to the literal symbol Ainit and an object corresponding to the control symbol Xinit. A matrix l:(X→Y,A →uv)is simulated as follows: first, object Xremoves a membrane with label Aby
the rules X→(l0)inA∈Rsand l0→l1δ∈RA; then, it creates membranes with labels u,vif u,vare non-terminal symbols, or sends u,vinto the environment if u,vare terminal symbols. Finally, the object Xchanges to Y.The rules X→#,#→#∈Rsguarantee that if the derivation of Gis “stuck” in a form which is not terminal, then the corresponding computation in Πwill enter an infinite loop. Finally, the result of a derivation in Gis terminal if and only if fis produced and no other non-terminal symbols have remained; this is checked by the rules f→#inA∈Rs(after the application of such a rule, the rule #→#∈RAthen guarantees that the corresponding computation in Πwill enter an infinite loop). Observing that the P system constructed above fulfills all the conditions stated in the theorem concludes the proof. We conjecture that we need not restrict the membrane structure, i.e., even the following should be true: PsMATλ=PsO1,1,∗P∗,∗,∗(ncoo, tar, mcre, δ). Number of Symbols The cardinality of the alphabet in the computational completeness proofs usually depends on the complexity parameters of the simulated device. We will now show that any recursively enumerable set of mdimensional vectors of non-negative integers can be generated by P systems with membrane creation and dissolution, having the alphabet of 10 + msymbols. Theorem 4 L(m)O2,2,10+mP1,∗,∗(ncoo, tar, mcre, δ) =RE(m). Proof. We simulate a register machine M=(2,T,P,l 0,l h) where T={ai|1≤i≤m};letP+denote the set of all ADD instruction labels, and let P−denote the set of all SUB instruction labels. Π=(O,H, [s[I]I]s,λ,b,R l0,···,R D), O=T∪{b, c, d, e}∪{r+,r −,r −|r∈{1,2}}, H=P∪{I,1,2,s,D}, Ri=Ri,I ∪Ri,O ∪Ri,A ∪Ri,S ∪Ri,D ∪Ri,Z ∪Ri,N ,i∈H. For clarity, the rules are grouped (initialization, output, add, subtract, decrement case, zero case, next instruction). Initialization: RI,I ={b→[l0d]l0}, Ri,I =∅,i∈H−{I}, Output: Rl,O =a→aout |l:(write(a),l),a∈T}, ∪{a→aδ |a∈T},l∈P∪{I}, Rs,O ={a→aoutb, a →aoutc|a∈T}, Ri,O =∅,i∈H−(P∪{I,s}), Add: Rl,A ={d→(r+)out |l:(A(r),l,l )∈P, r∈{1,2}} ∪ {r+→r+δ|r∈{1,2}}, l∈P∪{I}, Rs,A ={r+→[rd]r|r∈{1,2}}, Rr,A ={d→bout,d→cout},r∈{1,2}, RD,A =∅, Subtract: Rl,S ={d→(r−)out |l:(S(r),l,l )∈P, r∈{1,2}} ∪ {r−→r−δ|r∈{1,2}}, l∈P∪{I}, Rs,S ={r−→r −d, d →[Dd]D|r∈{1,2}}, RD,S ={d→λ}, Ri,S =∅,i∈H−P−{I,s,D}, Decrement case: Rs,D ={r −→(r −)inr,e→einD|r∈{1,2}}, Rr,D ={r−→r −d, d →[dd]D},r∈{1,2}, RD,D ={r −→eout},r∈{1,2}, Ri,D =∅,i∈H−{1,2,s,D}, Zero case: Rs,Z ={r −→(r −)inD}|r∈{1,2}}, RD,Z ={r −→bδ |r∈{1,2}}, Ri,D =∅,i∈H−{s, D}, Next instruction: Rs,N ={b→binl,c→cinl|l∈P}, Rl,N ={b→[la]l,c→[l a]l | l:(X(r),l,l)∈P, X ∈{A, S}}. The instruction labels are encoded into membrane labels, and the values of the registers are encoded by the number of copies of some membranes associated with them. The proof mainly relies on the fact that the amount of information needed to be transmitted between the instructions and the registers is “small”, i.e., the instructions tell us which operation (ADD or SUB, represented by r+,r −,r∈{1,2}) has to be applied and to which register rit has to be applied. The objects r −,r∈{1,2},and eare used to implement the SUB instruction, and the object dhere is used to organize a delay for the appearance checking, similar to the technique from Theorem 1, whereas otherwise it is used when the membranes already contain all the information needed. After an operation has been simulated, the next instruction is chosen from two variants, non-deterministically chosen in the ADD case and as well in the SUB case here depending on whether decrementing has been successful or not. These variants are represented by the objects b, c.The transition to the next instruction is done in the following way: Object bin membrane lcreates membrane l, or object cin membrane lcreates membrane l. After this, the object “memorizes” the next register to be operated on and the operation to be performed, and then membrane lis dissolved, leaving the newly created membrane in the skin. If we want to start with the simplest membrane structure, one more symbol is needed as is exhibited in the following:
Theorem 5 L(m)O1,2,11+mP1,∗,∗(ncoo, tar, mcre, δ) =RE(m). Proof. We here again simulate a register machine M= (2,T,P,l 0,l h)as in the proof of the preceding theorem, but in the P system Πwe use an additional symbol afor an initial step starting in the skin membrane: Π=(O,H, [s]s,a,R l0,···,R D), O=T∪{a, b, c, d, e}∪{r+,r −,r −|r∈{1,2}}, H=P∪{I,1,2,s,D}, Ri=Ri,I ∪Ri,O ∪Ri,A ∪Ri,S ∪Ri,D ∪Ri,Z ∪Ri,N ,i∈H. Initialization: Rs,I ={a→[Ib]I}, RI,I ={b→[l0d]l0}, Ri,I =∅,i∈H−{s, I}. Except for the initialization, the sets of rules are exactly the same as for the P system Πconstructed in the preceding proof, which observation already completes this proof. Figure 2 depicts the membrane structures of the P systems constructed in the succeeding proofs. Th. 6 s 1 1 ··· n1+1 @@2 HHHH2 ··· n2+1 XXXXXXs Th. 7 1 1 2@2 ··· n1+1 HH1 HH2 2@2 ··· n2+1 HH1 Th. 8 .1 (polarization 0) Figure 2. Membrane structures for active membrane proofs 4. One Polarization The theorem below provides a result, similar to that of Theorem 1, for P systems with active membranes with only one polarization (usually called P systems with active membranes without polarizations). The construction gives no upper bound on the number of objects present inside the system in general, but during any halting computation the number of objects never exceeds 3. Theorem 6 LO1,3/∗,∗P4,∗,3(active1,a,b,c,d,e)=RE. Proof. In the description of the P system Πbelow, wsdescribes the initial multiset for the skin membrane, whereas w sdenotes the initial multiset in the elementary membrane having the same label as the skin membrane. We now simulate a register machine M=(2,T,P,l 0,l h): Π=(O,μ,ws,w 1,w 2,w s,R), μ=[ s[1]1[2]2[s]s]s, O=T∪{ai|1≤i≤2}∪{l,l1,l 2|l∈P} ∪{b1,b 2,t,d,#}, ws=l0,w 1=w2=w s=λ, R=RO∪RA∪RS∪RD∪RZ. The rules are grouped in categories: output, add, subtract, decrement case and zero case. Output: RO={[l→la]s,[l→la]s,[a]s→[] sa |l:(write(a),l),a∈T}, Add: RA={l[] i→[l]i,[l]i→[l1]i[t]i, [t→λ]i,[l1]i→[] il, [l1]i→[] il | l:(A(i),l,l),i∈{1,2}}, Subtract: RS={[l→dbil1]s,b i[] i→[bi]i, [bi]i→[] it, [t→λ]s, [bi→#]s,[bi→#]i, [#→#]i|l:(S(i),l,l ),i∈{1,2}} ∪{d[] s→[t]s,[t→λ]s [d→#]s,[#→#] s}, Decrement case: RD={l1[] i→[l1]i,[l1]i→l |l:(S(i),l,l),i∈{1,2}}, Zero case: RZ={l1[] s→[l2]s,[l2]s→[] sl |l∈P−}. Like in the previous theorem, we simulate a register machine with output tape and two registers; the values of registers i,i∈{1,2}, are represented by the multiplicities of membranes i. However, since new membranes can only be created by dividing existing ones, one extra membrane is needed for every register. The duty of dis to “keep busy” the elementary membrane with label s(otherwise #appears and the computation does not halt), and the use of the objects biis to “keep busy” one membrane with label ifor two steps. Object tis not needed for the computation, it is only used to keep the usual form of membrane division and communication rules, it is immediately erased. Generating an output is done by a non-cooperative rule changing the instruction label and producing the corresponding symbol, which is then sent out. Incrementing a register (l:(A(i),l,l )) is done in the following way: l enters membrane i(there is always at least one), dividing it. The object l1in one copy is sent to the skin as lor l, while the object tin the other copy is erased. Subtracting with (l:(S(i),l,l)) is done by keeping busy the elementary membrane with label sfor one step and one membrane with label ifor two steps, while object l1tries to enter any membrane with label i. If the register is not zero, then l1enters one of the other membranes with label i, dissolves it, and changes to l. Otherwise, after having waited for one step, object l1enters the elementary membrane with label sand returns to the skin as l . During a correct simulation of a run of the register machine (in particular, during any halting computation) there are never more than 3 objects present inside the system.
It is possible to reduce the number of membrane labels to two at the price of starting with seven membranes. Theorem 7 LO1,3/∗,∗P7,∗,2(active1,a,b,c,d,e)=RE. Proof. (sketch) In a way quite similar to the proof of Theorem 1, let us now start with a membrane structure [1[1[1]1[2]2]1[2[1]1[2]2]2]1(see also Figure 2), represent the values of a working register iby the number of elementary membranes with label 2, inside the membranes with labels i, minus one. The elementary membranes with label 1will be used for delay, just like the elementary membrane labelled by swas used in the proof of Theorem 6, and the instructions are simulated accordingly. The main difference is that when simulating an ADD or a SUB instruction we have one additional initial step at the beginning choosing the “cluster membrane” representing the corresponding register (see the proof of Theorem 1). Obviously, at the end of the simulation of the instruction in the right “cluster membrane”, we need an additional final step for moving the instruction label back to the skin membrane. 5. Two Polarizations The last theorem established in this paper shows that with two polarizations we need only one membrane to simulate register machines in a deterministic way: Theorem 8 DPsaOP1,1,1(active2,a,c)=PsRE. Proof. We will simulate the actions of a deterministic register machine M=(d, P, l0,l h)with dregisters by a deterministic P system with one membrane and two polarizations. For every instruction l, let us denote the register lacts on by r(l)and the operation lcarries out by op(l). Π=(O,{0,1},[1]0 1,(l0,0,0),R), O={(a, i, j)|1≤i≤d, 0≤j≤d+2} ∪{(l,i,j)|l∈P,0≤i≤2, 1≤j≤d+2}∪{#},. The system receives the input (a, 1,0)n1···(a, d, 0)ndin addition to w1in the skin membrane. The set Rcontains the following rules [z]e 1→[] 1−e 1z, e ∈{0,1},(1) [(a, i, j)→(a, i, j +1) ]0 1,1≤i≤d, 0≤j≤d+1,(2) [(a, i, d +2)→(a, i, 0) ]0 1,1≤i≤d, (3) [(a, i, j +1) ]1 1→[] 0 1(a, i, j +1), 1≤i≤d, (4) [(l,0,j)→(l,0,j+1) ]0 1,l∈P, 0≤j<r(l)−1,(5) [(l,i,j)→(l, i,j +1) ]0 1,l∈P, i ∈{1,2}, r(l)≤j≤d+1,(6) [(l,1,d+2)→(l,0,0) ]0 1,l∈P, (7) [(l,2,d+2)→(l,0,0) ]0 1,l∈P, (8) [(l,0,j)→(l,1,j+1)(a, j, j +1) ]0 1,l∈P, j=r(l)−1,op(l)=A, (9) [(l,0,j)→(l,0,j+1)z]0 1,l∈P, j=r(l)−1,op(l)=S, (10) [(l,0,j)→(l,0,j+1) ]0 1,l∈P, j=r(l),op(l)=S, (11) [(l,0,j)→(l,0,j+1) ]1 1,l∈P, j=r(l)+1,op(l)=S, (12) [(l,0,j)→(l,1,j+1) ]0 1,l∈P, j=r(l)+2,op(l)=S, (13) [(l,0,j)→(l,2,j)z]1 1,l∈P, j=r(l)+2,op(l)=S, (14) [(l,2,j)→(l,2,j+1) ]1 1,l∈P, j=r(l),op(l)=S, (15) [(lh,0,0) ]0 1→[] 1 1(lh,0,0),1≤i≤d. (16) The idea of this proof is similar to the one from [2, 3]: the symbols corresponding to the registers have states (second subscript) 0,···,d+2, and so do the symbols corresponding to the instructions of the register machine. The first subscript of the instruction symbols is 0if the instruction has not yet been applied, and it is 1if increment or decrement has been applied, and 2if the decrement has failed. Most of the time the polarization is 0; object zcan reverse the polarization by (1). When the polarization is 0,the register symbols cycle through the states by (2), (3). Before the current instruction lis applied, the instruction symbols also cycle through the states until the state becomes r(l)−1, i.e., the index of the register (the instruction operates on) minus one. We will explain the details of the application below. After the instruction has been applied, the first subscript of the instruction symbol changes to 1or 2and it cycles through the states by (6), finally changing into lby (7) or into l by (8). Addition is done by rule (9). Decrement is done by a “diagonalization technique”: polarization 1when register iis in state i+1signals a decrement attempt of register iby (4), and the polarization will change if and only if it has been successful. Thus, to apply l:(S(i),l,l ),the instruction symbol in state i−1additionally produces a symbol z. By the time zchanges the polarization to 1by (1), all other symbols reach state i+1. After one more step the state symbol checks whether the decrement has been