Symport/Antiport P Systems with Three Objects Are Universal

Symport/Antiport P Systems with Three Objects Are Universal Gheorghe P˘aun1,2, Juan Pazos3, Mario J. P´erez-Jim´enez2, Alfonso Rodr´ıguez-Pat´on3 1Institute of Mathematics of the Romanian Academy PO Box 1-764, 014700 Bucure¸sti, Romania E-mail: [email protected] 2Research Group on Natural Computing Department of Computer Science and Artificial Intelligence University of Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain E-mail: gpaun/[email protected] 3Department of Artificial Intelligence, Faculty of Computer Science Polytechnical University of Madrid Campus de Montegancedo Boadilla del Monte 28660, Madrid, Spain E-mail: jpazos/[email protected]pm.es Abstract. The operations of symport and antiport, directly inspired from biology, are already known to be rather powerful when used in the framework of P systems. In this paper we confirm this observation with a quite surprising result: P systems with symport/antiport rules using only three objects can simulate any counter machine, while systems with only two objects can simulate any blind counter machine. In the first case, the universality (of generating sets of numbers) is obtained also for a small number of membranes, four. 1 Introduction P systems with symport/antiport [8] use as rules for processing the symbol-objects operations coming from biology, namely simultaneous trans-membrane transportation of several chemicals, either in the same direction (and this is called symport) or in opposite directions (which is called antiport) – biochemical details can be found in [1]. Since a considerable degree of cooperation (context-sensitivity) among objects is available, it is 1 somewhat expected that the systems of this type are universal, equal in power with Turing machines, for various combinations of ingredients (number of membranes, size of symport or antiport rules). Not so expected is the fact that such systems are universal even when using minimal symport/antiport rules, moving at most one object in each direction; the currently strongest results of this type state the universality for systems with three membranes, [2], [12], without knowing whether two membranes suffice in order to reach the universality. We start here a somewhat “orthogonal” direction of research: we let free the number of membranes and the size of rules, and concentrate on the number of objects used in a system. Can this number be bounded? If so, which is the price (which other parameters should grow)? Which is the smallest number of objects which ensures the universality? That a bound on the number of objects can be imposed is again somewhat expected, for instance, having in mind that there are small universal Turing machines (with the size estimated in both the number of tape symbols and of states – which can be simultaneously bounded at rather low values), see, e.g., [10]. However, there is no direct simulation of a Turing machine by a P system with symport/antiport rules, hence the results about small universal Turing machines cannot be used in our framework. (Furthermore, Turing machines use the positional information provided by the tape, while here we do not have such a data structure, we work with multisets of symbol-objects.) The bound we find here on the number of objects is surprisingly small: three objects suffice. The proof is based on a unary codification of all numbers we deal with in a P system (which simulates a counter machine), with two additional symbols necessary in order to control the work of the system. One of these additional objects can be saved when simulating blind counter machines. 2 Prerequisites We introduce here both the definition of P systems with symport/antiport rules, the class of P systems we investigate, and that of counter machines, the tool used in the proof of our result – but the reader is supposed to have some familiarity with membrane computing, for instance, from [9]; details can be found at the web address http://psystems.disco.unimib.it. A P system with symport/antiport rules is a construct of the form Π = (O, H, µ, w1,...,wm, E, R1, . . . , Rm, io), where Ois the alphabet of objects, His the finite set of labels for membranes (in general, one uses natural numbers as labels), µis the membrane structure (of degree m≥1, with the membranes labelled in a one-to-one manner with elements of H; as usual, we represent the membrane structures by strings of matching labelled parentheses), w1, . . . , wmare strings over Orepresenting the multisets of objects present in the mcompartments of µin the initial configuration of the system, E⊆Ois the set of objects supposed to appear in the environment in arbitrarily many copies, R1,...,Rmare the (finite) sets of rules associated with the mmembranes of µ, and io∈His the label of a membrane of µ, which indicates the output region of the 2 system (note that we do not impose that the output region is enclosed by an elementary membrane – although in the main result of the paper, as well as in many papers from the literature, this is the case). The rules from Rcan be of two types (by O+we denote the set of all non-empty strings over O, with λdenoting the empty string): –Symport rules, of the forms (x, in) or (x, out), where x∈O+. When using such a rule, the objects specified by xenter or exit, respectively, the membrane with which the rule is associated. In this way, objects are sent to or imported from the surrounding region – which is the environment in the case of the skin membrane. (The length of xin a symport rule is called the weight of the rule.) –Antiport rules, of the form (x, out;y, in), where x, y ∈O+. When using such a rule for a membrane i, the objects specified by xexit the membrane and those specified by yenter from the region surrounding membrane i; this is the environment in the case of the skin membrane. (The maximal length of x, y is called the weight of the rule.) The rules are used in the non-deterministic maximally parallel manner, standard in membrane computing. In this way, we obtain transitions from a configuration of the system to the next configuration. A sequence of transitions constitutes a computation, and a computation halts when a configuration is reached where no rule can be applied. The number of objects present in region ioin the halting configuration is said to be computed by the system along that computation; the set of all numbers computed in this way by Π is denoted by N(Π). The family of all sets N(Π) of numbers computed as above by P systems with at most mmembranes, using symport rules of weight at most rand antiport rules of weight at most q, for m≥1 and r, q ≥0, is denoted by NOPm(symr, antiq). By NRE we denote the family of Turing computable sets of natural numbers. Many results of the form NRE =NOPm(symr, antiq) are known, for various combinations of the parameters m, r, q – see [2, 3, 9, 12], etc. Here we consider one further parameter: the cardinality of the set Oof objects. By NOPm(objn, symr, antiq) we denote the family of sets of numbers N(Π) computed by P systems with at most mmembranes, at most nobjects, and symport and antiport rules of weight at most r, q, respectively. When one of these parameters is not bounded, we replace it with ∗. Thus, NOPm(symr, antiq) corresponds to the family NOPm(obj∗, symr, antiq). In order to also compute sets of vectors, as done in several cases in membrane computing, we cannot proceed in the usual way, distinguishing the objects from the output membrane and considering their multiplicities, but we can consider several output membranes: instead of io, we take io,1, io,2, . . . , io,k, for some k≥1. Thus, if we halt with multisets z1, z2, . . . , zkin these membranes, then we have computed the vector (|z1|,|z2|,...,|zk|) (where |z|is the lenght of the string z, hence the total multiplicity of the multiset represented by z). In this case, we denote by P s(Π) the set of all vectors computed by a system 3 Π and by P sOPm(objj, symr, antiq) the family corresponding to NOPm(objj, symr, antiq). In turn, we denote by P sRE the family of Turing computable sets of vectors of natural numbers. In the proof from the next sections we will use counter machines as devices characterizing PsRE (hence also NRE), hence the Turing computability. In various places, one uses various names for the same device, sometimes with different formalisms and slight differences in architecture and functioning: register machines, program machines, multi-counter machines, etc.; we adhere here to the following terminology and definition. Informally speaking, a counter machine consists of a specified number of counters which can hold any natural number, and which are handled according to a program consisting of labelled instructions; the counters can be increased or decreased by 1 – the decreasing being possible only if a counter holds a number greater than or equal to 1 (we say that it is non-empty) –, and checked whether they are non-empty. Formally, a (non-deterministic) counter machine is a device M= (m, B, l0, lh, R), where m≥1 is the number of counters, Bis the (finite) set of instruction labels, l0is the initial label, lhis the halting label, and Ris the finite set of instructions labelled (hence uniquely identified) by elements from B(Ris also called the program of the machine). The labelled instructions are of the following forms: –l1: (ADD(r), l2, l3), 1 ≤r≤m(add 1 to counter rand go non-deterministically to one of the instructions with labels l2, l3), –l1: (SUB(r), l2, l3), 1 ≤r≤m(if counter ris not empty, then subtract 1 from it and go to the instruction with label l2, otherwise go to the instruction with label l3), –lh:HALT (the halt instruction, which can only have the label lh). A counter machine generates a k-dimensional vector of natural numbers in the following manner: we distinguish kcounters as output counters (without loss of generality, they can be the first kcounters), and we start computing with all mcounters being empty, with the instruction labelled by l0; if the computation reaches the instruction lh:HALT (we say that it halts), then the values of counters 1,2, . . . , k is the vector generated by the computation. The set of all vectors from Nkgenerated in this way by Mis denoted by Ps(M). If we want to generate only numbers (1-dimensional vectors), then we have the result of a computation in counter 1, and the set of numbers computed by Min this way is denoted by N(M). It is known (see [7], [3]) that non-deterministic counter machines with k+ 2 counters can compute any set of Turing computable k-dimensional vectors of natural numbers (hence machines with three counters generate exactly the family NRE, of Turing computable sets of numbers). In the case when a counter machine cannot check whether a counter is empty one say that it is blind: the counters are increased and decreased by one as usual, but if the machine tries to subtract from an empty counter, then the computation aborts without producing any result. It is known (see, e.g., [5]) that blind counter machines are strictly less powerful than general counter machines (hence than Turing machines). 4 3 Universality with Three Objects We pass now to giving the universality result mentioned in the Introduction. Theorem 3.1 P sOP∗(obj3, sym∗, anti∗) = P sRE. Proof. We only prove the relation PsRE ⊆NOP∗(obj3, sym∗, anti∗), the converse inclusion being straightforward (we can also invoke the Turing-Church thesis for it). Let us consider a counter machine M= (m, B, l0, lh, R) with mcounters. We assume that Mis non-trivial, that is, l06=lhand Rcontains at least one instruction, and that the output counters are the first k, that is, 1,2, . . . , k. We construct a P system Π with m+ 1 membranes which will compute the same set of vectors as M. Essential in the construction is the following codification of certain relevant information items related to M. Consider the following set: J=B∪ {(l1, addr)|l1: (ADD(r), l2, l3)∈R} ∪ {(l1, subr>0),(l1, subr=0)|l1: (SUB(r), l2, l3)∈R}. Assume that Jcontains nelements, J={α1, . . . , αn}(their ordering is not relevant). Clearly, n≥3: we have at least two labels and at least one instruction. Then, with each element αiwe associate the natural number v(αi) = 8n+ 8i, 1≤i≤n. We denote v(J) = {v(αi)|1≤i≤n}. Three facts about these numbers are important for what follows: 1. v(αi)≥32 for all 1 ≤i≤n(because n≥3), 2. each number v(αi) is strictly bigger than the half of any other number v(αj),1≤ i, j ≤n(hence no number v(αi) can be written as the sum of any two or more than two numbers from v(J)), 3. if we subtract any number t, 1≤t≤7, from any v(αi), we do not get the value of any v(αj),1≤i, j ≤n. Now, the system we look for is Π = (O, H, µ, w0, w1, w2, . . . , wm, E, R0, R1, R2, . . . , Rm, io,1, io,2, . . . , io,k), where: O={a, b, c}, H={0,1,2, . . . , m}, µ= [0[1]1[2]2. . . [m]m]0(0 is the label of the skin membrane), w0=av(l0)c, wi=λ, for all 1 ≤i≤m, E=O, io,j =i, 1≤j≤k, 5 and the sets of rules are constructed as follows. Let us firstly explain shortly the idea behind the construction. All labels of instructions from Rand the actions of these instructions – the operations of increasing or decreasing a counter – are codified in base 1, through the mapping v, in the number of occurrences of object a. The copies of object arepresenting a given element of the set Jwill always evolve together, otherwise the computation will never stop. In order to represent the values of counters, we use the object b: the number of copies of bfrom a membrane r= 1,2, . . . , m represents the value stored in counter r. When simulating a subtraction instruction, we first guess whether the counter to modify is empty or not. When a wrong guess is made, as well as in any case when a step in Π does not correctly simulate a step in M, the computation will never end. To this aim we will use a third object, c, subject of a rule of the form (cc, out;cccc, in), which can indefinitely “flood” the system with copies of c. When the label lhis reached, the computation will stop. These general ideas are implemented as follows. 1. For each instruction l1: (ADD(r), l2, l3)∈R, the set R0contains the rules 1. (av(l1), out;av(l1,addr)b, in), 2. (av(l1,addr), out;av(l2), in),if l26=lh, 2′. (av(l1,addr), out),if l2=lh, 3. (av(l1,addr), out;av(l3), in),if l36=lh, 3′. (av(l1,addr), out),if l3=lh, and the set Rr(corresponding to this instruction) contains the rules: 4. (av(l1,addr)b, in), 5. (av(l1,addr), out). 2. For each instruction l1: (SUB(r), l2, l3)∈R, we introduce the following rules in R0 6. (av(l1), out;av(l1,subr>0), in), 7. (av(l1,subr>0)b, out;av(l2), in),if l26=lh, 7′. (av(l1,subr>0)b, out),if l2=lh, 8. (av(l1), out;av(l1,subr=0)c, in), 9. (av(l1,subr=0)c13, out;av(l3), in),if l36=lh, 9′. (av(l1,subr=0)c13, out),if l3=lh, and the set Rr(corresponding to this instruction) contains the rules: 10. (av(l1,subr>0), in), 11. (av(l1,subr>0)b, out), 12. (av(l1,subr=0), in), 6 13. (av(l1,subr=0)b, out), 14. (av(l1,subr=0), out;c, in). 3. We also introduce the following rules in R0(let us call them “flooding rules”) 15. (a, out;c27, in), 16. (cc, out;c4, in), 17. (b, out;c27, in), and the following rules in each set Rr,1≤r≤m: 18. (a, out;c, in), 19. (c, out). The simulation of the instruction l1: (ADD(r), l2, l3)∈Rproceeds as follows. When av(l1)is present in the skin region, rule 1 can be used, bringing inside av(l1,addr)b. Note that if not all copies of awere used by this rule (that is, a rule with a smaller number of a was applied), then the remaining copies of ashould exit by means of the “flooding” rule 15, which brings inside 27 copies of c. The rule 16 will be used forever, bringing inside more and more copies of c. It is important to note here that the only possibility to send out copies of cis by rules 9 and 9′; each time we remove 13 copies of c. However, rules 15 and 17 bring inside 27 copies of cat once; even if 13 of them will be sent out, 14 will remain, hence more than a rule of types 9 and 9′can remove. Moreover, rules of types 9 and 9′cannot be used in consecutive steps, we need at least one step in between. Thus, the 14 copies of chave to evolve at least one step in the system, and they can evolve in various manners: get doubled by rule 16, or enter membrane r, provided that copies of aare present there; from membrane rthey exit in the next step and have to repeat these operations. Moreover, any abrought outside membrane rwill again bring 27 copies of cinside (if some copies of aremain in membrane r, they cannot be equal to any v(α) from v(J), hence they cannot exit the system. In all cases, the computation will never stop, the number of copies of c will increase continuosly. (The number 27 from rules of types 15 and 17 is not the smallest one which can ensure the non-halting behavior of the system in case of “wrong” steps, but this number makes clearer the non-halting and the explanations about the behavior of Π.) Now, by means of rule 4, av(l1,addr)bcan enter membrane r. Again, any other move leads to an endless computation, because any other rule will leave copies of aunused, hence rule 15 should be applied. Now, if av(l1,addr)bis inside membrane r, we can use a rule of type 5 and send out of this membrane the multiset av(l1,addr), which amounts at increasing by one the value of counter r, represented by the number of copies of bpresent in membrane r. Again, all copies of ashould be used: any other rule than the one of type 5 which uses all copies of awill leave unused at eight three copies of a; one of them will exit by means of rule 18, the other seven will remain in the membrane. In this way, in 7 the skin region we cannot use any rule for all copies of apresent here, hence at least one will exit by means of rule 15, and the computation will never stop. In the case of the correct use of rules, av(l1,addr)should now exit the system by a rule of type 2 or 3, non-deterministically chosen, but in such a way that all copies of aare used. Thus, we bring inside av(l2)or av(l3), which is the correct continuation of the computation in M. If one of l2and l3is equal to lh, then av(l1,addr)should exit the system by a rule 2′or 3′, and the computation halts. Let us consider now a subtract instruction l1: (SUB(r), l2, l3)∈R. We start with av(l1) present in the skin region. We choose non-deterministically either a rule of type 6 or one of type 8. The first case corresponds to the guess that counter ris non-empty, the latter case corresponds to the guess that counter ris empty. Assume that we have chosen the first path, hence we have brought inside av(l1,subr>0). The continuation is similar to that from the case of addition, with the difference that now we remove a copy of bfrom membrane r, instead of bringing here one additional copy of b. First, by means of rule 10, av(l1,subr>0)is introduced in membrane r; if there is no copy of bhere (hence the guess that the counter is non-empty was wrong), then we cannot use the corresponding rule 11, hence at least eight copies of aremains inside; this means that rule 18 can be used, and the computation never ends. If the guess was correct, hence counter r(membrane r) is non-empty, then rule 11 is used, av(l1,subr>0)barrives in the skin membrane, and from here it exits the system by rule 7, which brings inside the code of l2, the correct continuation of the simulation. In all cases where a rule different from those mentioned above is used, at least one copy of awill remain in the skin region for rule 15, and the computation will continue forever. As above, this is ensured by the fact that all values v(α), α ∈J, are different from each other by at least eight units. If the label l2is equal to lh, then instead of rule 7 we use rule 7′and the computation stops. More complicated is the case when the counter ris empty. We start by bringing av(l1,subr=0)cinside the system, by rule 8. The multiset av(l1,subr=0)cannot be sent out (without leaving copies of ainside, and triggering “flooding” rules) by any other rule than one of type 9, which needs 13 copies of c; however, this multiset cannot stay in the skin region until such copies are brought into the system by rule 16, because rule 15 should be used, flooding the system with copies of c. Therefore, we have to use rule 12, and introduce av(l1,subr=0)in membrane r. Simultaneously, rule 16 uses the remaining copy of cand the copy already existing, and brings inside the system four copies of c. In the next step, if membrane rcontains at least one copy of b, hence the guess was wrong, then we have to use rule 13, and bring av(l1,subr=0)bin the skin region. No rule can now use the object bthan the one of type 17, and the computation will never stop. If the membrane rcontains no object b(hence the counter rwas empty), then av(l1,subr=0)must remain inside, and this is possible without compromising the computation, because the copies of cfrom the skin region can be “kept busy” by rule 16. This rule will bring 8 copies of cin the system. 8 We have two possibilities: to use rule 14 or not. Assume that we do not use it. Then, the 8 copies of cshould evolve by rules 16 and 18. Irrespective how many times we use rule 18, we can bring outside at most eight copies of a, which is not a number from v(J), hence these copies of awill evolve in the next step by the flooding rule 15. If only rule 16 has been used, then the number of copies of cis doubled, we have now 16 in the skin region. The reasoning continues. If we do not use rule 14, then either we bring outside membrane rat most 16 copies of a– again less than any code v(α), hence the flooding rule 15 must be used – or we double the copies of c, that is, we get 32 copies; this is more than 27, the computation will never end. Therefore, rule 14 must be used. Because no number from v(J) can be written as the sum of other numbers, this rule can be used only once. Assume that we use if for a wrong instruction, that is, not removing all copies of afrom membrane r. This means that at least 8 copies of aremains in membrane r. If we are in the step when we had 8 copies of cin the skin membrane, simultaneously, the 7 copies which are not used by rule 14 either bring copies of aout of membrane ror, at most six of them, get doubled by rule 16. In any case, out of membrane rwe cannot get the code of a correct instruction, hence we can only use rule 16 for at most three pairs of cand rule 18 for the remaining copy. We have now 13 available copies of cfor using rule 9 (or 9′), but one copy of ahas remained in the skin region and will flood the system with copies of c. In the case when we have 16 copies of cin the skin membrane, in the step when rule 14 is used (bringing a multiset av(l,subp=0)out of membrane r– remember that we discuss the case when rule 14 is used for a wrong instruction) we have 15 remaining copies of c in the skin membrane. If in membrane rwe have exactly 8 objects, we can bring them out by means of 8 copies of c(rule 18), while 6 of the other 7 copies of cwill use rule 16, leading to a total of 13 copies of cin the skin membrane. This means that in the skin membrane we have both completed the correct number of copies of afor recomposing the value of v(l1, subr=0) and 13 copies of c; we can exit by a rule 9 or 9′. However, 9 copies of care inside membrane r. In the next step, they exit membrane r, while a rule of types 1, 6 or 8 is used. The continuations from rules of types 1 and 6 have no way to remove c (without leaving copies of ainside the system). Assume that we have used a rule of type 8, hence again dealing with a subtraction where we guess that a counter is empty. There is no way to remove 9 copies of cin the next step, hence the number of cwill become 17. In the meantime, the multiset of copies of ahas entered a membrane q. Let us look to the possibilities for the 17 copies of cfrom the skin membrane in the next step. The number is odd, hence at least one copy of ccannot be used by rule 16, hence copies of awill be brought out of membrane p. If we use only rule 18, we cannot reach the value of any v(α), the copies of afrom the skin region will flood the system with copies of c. Thus, we have to use rule 14. If we bring all copies of aoutside membrane p (this happens irrespective whether there is any bhere, which is not correct with respect to M), then the other 16 copies of cwill get doubled; 13 copies of ccan exit by a rule 9 or 9′, but the other 19 which remain will get doubled by rule 16, and the computation will never stop. 9 [2] A. Alhazov, M. Margenstern, V. Rogozhin, Y. Rogozhin, S. Verlan, Communicative P systems with minimal cooperation. In G. Mauri, Gh. P˘aun, M.J. P´erez-Jim´enez, G. Rozenberg, A. Salomaa, eds., Membrane Computing. International Workshop WMC5, Milan, Italy, 2004. Revised Papers, Lecture Notes in Computer Science, Springer-Verlag, Berlin, 2005 (to appear). [3] R. Freund, A. P˘aun, Membrane systems with symport/antiport rules: universality results. In Gh. P˘aun, G. Rozenberg, A. Salomaa, C. Zandron, eds., Membrane Computing. International Workshop, WMC 2002, Curtea de Arge¸s, Romania. Revised Papers, Lecture Notes in Computer Science, 2597, Springer-Verlag, Berlin, 2002, 270–287. [4] R. Freund, Gh. P˘aun, M.J. P´erez-Jim´enez, Tissue-like P systems with channel-states. Brainstorming Week on Membrane Computing, Sevilla, February 2004, TR 01/04 of Research Group on Natural Computing, Sevilla University, 2004, 206–223, and Theoretical Computer Science, 2004, in press. [5] S.A. Greibach, Remarks on blind and partially blind one-way multicounter machines. Theoretical Computer Science, 7 (1978), 311–324. [6] C. Mart´ın-Vide, Gh. P˘aun, J. Pazos, A. Rodr´ıguez-Pat´on, Tissue P systems. Theoretical Computer Science, 296, 2 (2003), 295–326. [7] M. Minsky, Computation – Finite and Infinite Machines. Prentice Hall, Englewood Cliffs, NJ, 1967. [8] A. P˘aun, Gh. P˘aun, The power of communication: P systems with symport/antiport. New Generation Computing, 20, 3 (2002), 295–306. [9] Gh. P˘aun, Computing with Membranes – An Introduction. Springer-Verlag, Berlin, 2002. [10] Y. Rogozhin, Small universal Turing machines. Theoretical Computer Science, 168 (1996), 215–240. [11] P. Sosik, J. Matysek, Membrane computing: when communication is enough. In C.S. Calude, M.J. Dinneen, F. Peper, eds., Unconventional Models of Computation 2002, Lecture Notes in Computer Science, 2509 Springer-Verlag, Berlin, 2002, 264–275. [12] G. Vaszil, On the size of P systems with minimal symport/antiport. Pre-Proceedings of Workshop on Membrane Computing, WMC5, Milano, Italy, June 2004, 422–431. 16