Generalized P Colonies with passive environment

Generalized P Colonies with passive environment Lucie Ciencialov´a, Ludˇek Cienciala, and Petr Sos´ık Research Institute of the IT4Innovations Centre of Excellence, Faculty of Philosophy and Science, Silesian University in Opava, Czech Republic {lucie.ciencialova,ludek.cienciala,petr.sosik}@fpf.slu.cz Summary. We study two variants of P colonies with initial content of P colony and so called passive environment: P colonies with two objects inside each agent that can only consume or generate objects, and P colonies with one object inside each agent using rewriting and communication rules. We show that the first kind of P colonies with one consumer agent and one sender agent can generate all sets of natural numbers computed by register machines, and hence they are computationally universal in the Turing sense. Similarly, also the second kind of systems with three agents with rewriting/consuming rules is computationally complete. The paper improves previously published universality results concerning generalized P colonies, and it also extends our knowledge about very simple multi-agent systems capable of universal computation. Key words: P colony, computational completeness, register machine 1 Introduction P colony was introduced in [9] as a very simple variant of membrane systems inspired by so called colonies of formal grammars. See [11] for more information about membrane systems and [7] for details on grammar systems theory. There are three basic entities in the P colony model: objects, agents and the environment. A P colony is composed of agents, each containing a collection of objects embedded in a membrane. The objects can be placed in the environment, too. Agents are equipped with programs composed of rules that allow interactions of objects. The number of objects inside each agent is set by definition and it is usually very low – 1, 2 or 3. The environment of P colony serves as a communication channel for agents: an agent is able to affect the behaviour of another agent by sending objects via the environment. There is also a special type of environmental objects denoted by ewhich are present in the environment in an unlimited number of copies. A specific variant of P colony called eco-P colony with two object inside each agent, where the environment can change independently on the agents, was introduced in [1]. The evolution of the environment is controlled by a 0L scheme 152 L. Ciencialov´a, L. Cienciala, P. Sos´ık applying context free rules in parallel to all possible objects in the environment which are unused by the agents in the current step of computation. The activity of agents is based on rules that can be rewriting, communication or checking; these three types was introduced in [9]. Furthermore, generating, consuming and transporting rules were introduced in [5]. Rewriting rule a→ballows an agent to rewrite (evolve) one object aplaced inside the agent to object b. Communication rule a↔bexchanges one object cplaced inside the agent for object dfrom the environment. Checking rule r1/r2,where each of r1, r2is a rewriting or a communication rule, sets a priority between these two rules. The agent try to apply the first rule and if it cannot be performed, the agent executes the second rule. Generating rule a→bc creates two objects b, c from one object a. Consuming rule ab →crewrites two objects a, b to one object c. Transporting rule of the form (a in) or (a out) is used to transport one object from the environment into the agent, or from the agent to the environment, respectively. The rule is always associated with a consuming/generating rule to keep a constant number of object inside the agent. The rules are combined into programs in such a way that all object inside the agent are affected by execution of the rules in every step. Consequently, the number of rules in the program is the same as the number of object inside the agent. The programs that contain consuming rules are called consuming programs and the programs with generating rules are called generating programs. The agent that only contains consuming resp. generating programs is called consumer resp. sender. P colonies with senders and consumers without evolving environment were studied in [5] and the authors proved their computational completeness (in the Turing sense), as well as computational completeness of P colonies with senders and consumers with 0L scheme for the environment. Many papers were devoted to P colonies with rewriting and communication rules without evolving environment, e.g., [4, 6, 8], and there are two book chapters in [2] and [11] describing this topic. In this paper we focus on P colonies with initial content of P colony with “passive” environment. The paper is structured as follows: The second section is devoted to definitions and notations used in the paper. The third section contains results obtained during studies of P colonies with senders and consumers. In the fourth section we study P colonies with one object inside the agent and rewriting/communication rules. The paper concludes with a summary of presented results. 2 Definitions Throughout the paper we assume the reader is familiar with basic of formal automata and language theory. We introduce notation used in the paper. Generalized P Colonies with passive environment 153 We use N·RE to denote the family of recursively enumerable sets of natural numbers and Nto denote the set of natural numbers. Σis a notation for the alphabet. Let Σ∗be set of all words over alphabet Σ(including the empty word ε). For the length of the word w∈Σ∗we use the notation |w|and the number of occurrences of symbol a∈Σin wis denoted by |w|a. Amultiset of objects Mis a pair M= (V, f), where Vis an arbitrary (not necessarily finite) set of objects and fis a mapping f:V→N;fassigns to each object in Vits multiplicity in M. The set of all multisets over the set of objects Vis denoted by V∗. The cardinality of M, denoted by card(M), is defined by card(M) = Pa∈Vf(a). Any multiset of objects Mwith the set of objects V={ai,...an}can be represented as a string wover alphabet Vwith |w|ai=f(ai); 1 ≤i≤n. Obviously, all words obtained from wby permuting the letters can also represent M, and εrepresents the empty multiset. The mechanism of evolution of the environment is based on a 0L scheme. It is a pair (Σ, P), where Σis the alphabet of 0L scheme and Pis the set of context free rules fulfilling the condition ∀a∈Σ∃α∈Σ∗such that (a→α)∈P. For w1, w2∈Σ∗we write w1⇒w2if w1=a1a1. . . an, w2=α2α2. . . αn, for ai→αi∈P, 1≤i≤n. Aregister machine [10] is the construct M= (m, H, l0, lh, P) where: -mis a number of registers, His a set of instruction labels, -l0is an initial/start label, lhis the final label, -Pis a finite set of instructions injectively labelled with the elements from the given set H. The instructions of the register machine are of the following forms: l1: (ADD(r), l2, l3) Add 1 to the contents of the register rand proceed to the instruction (labelled with) l2or l3. l1: (SUB(r), l2, l3) If the register ris not empty, then subtract 1 from its contents and go to instruction l2, otherwise proceed to instruction l3. lh:HALT Stop the machine. The final label lhis only assigned to this instruction. Without loss of generality, one can assume that in each ADD-instruction l1: (ADD(r), l2, l3) and in each conditional SUB-instruction l1: (SUB(r), l2, l3) the labels l1, l2, l3are mutually distinct. The register machine Mcomputes a set N(M) of numbers in the following way: we start with all registers empty (hence storing the number zero) with the instruction with label l0and we proceed to apply the instructions as indicated by the labels (and made possible by the contents of registers). If we reach the halt instruction, then the number stored at that time in the register 1 is said to be computed by Mand hence it is introduced in N(M). (Because of the nondeterminism in choosing the continuation of the computation in the case of ADD-instructions, N(M) can be an infinite set.) The family of sets of numbers computed by register machines is denoted by N·RM. Theorem 1. [10] N·RM =N·RE. 154 L. Ciencialov´a, L. Cienciala, P. Sos´ık 2.1 Generalized P colonies Definition 1. A P colony with capacity c≥1is the structure Π= (Σ, e, f, vE, DE, B1, . . . , Bn),where •Σis the alphabet of the colony, its elements are called objects, •eis the basic (environmental) object of the colony, e∈Σ, •fis final object of the colony, f∈Σ, •vEis the initial content of the environment, vE∈(Σ− {e})∗, •DEis 0L scheme (Σ, PE), where PEis the set of context free rules, •Bi,1≤i≤n, are the agents, every agent is the structure Bi= (oi, Pi), where oiis the multiset over Σ, it defines the initial state (content) of the agent Bi and |oi|=cand Pi={pi,1, . . . , pi,ki}is the finite set of programs of three types: (1) generating program with generating rules a→bc and transporting rules d out - the number of generating rules is the same as the number of transporting rules. (2) consuming program with consuming rules ab →cand transporting rules d in - the number of consuming rules is the same as the number of transporting rules. (3) rewriting/communication program can contain three types of rules: a→b, called a rewriting rule, c↔d, called a communication rule, r1/r2, called a checking rule; each of r1, r2is a rewriting or a communication rules. Every agent has only one type of programs. The agent with generating programs is called sender and the agent with consuming programs is called consumer. The capacity of P colony with senders and consumers must be even number. The initial configuration of a P colony is the (n+ 1)-tuple (o1, . . . , on, vE), with symbols o1, . . . , on, vEas in Definition 1. In general, the configuration of the P colony Πis defined as (n+ 1)-tuple (w1, . . . , wn, wE), where wirepresents the multiset of objects inside i-th agent, |wi|=c, 1≤i≤n, and wE∈(Σ− {e})∗is the multiset of objects different from eplaced in the environment. At each step of the (parallel) computation every agent tries to find one of its programs to apply. If the number of applicable programs is higher than one, the agent non-deterministically chooses one. At each step of computation, the set of active agents executing a program must be maximal, i.e., no further agent can be added to it. By applying programs, the P colony passes from one configuration to another configuration. Objects in the environment unaffected by any program in the given step are rewritten by the 0L scheme DE.A sequence of configurations starting from the initial configuration is called a computation. A configuration is halting if the P colony has no applicable program. Each halting computation has associated Generalized P Colonies with passive environment 155 aresult – the number of copies of the final object placed in the environment in halting configuration. N(Π) = {|wE|f|(o1, . . . , on, vE)⇒∗(w1, . . . , wn, wE)}, where (o1, . . . , on, vE) is the initial configuration, (w1, . . . , wn, wE) is the final configuration, and ⇒∗denotes reflexive and transitive closure of ⇒. Let us denote NEPCOL(i, j, k, u, v, w) the family of the sets computing by P colonies with at most j≥1 agents with i≥1 objects inside the agent and with at most k≥1 programs associated with each agent such that: u=check if the P colony uses rewriting/communication rules with checking rules u=no-check if the P colony uses rewriting/communication rules without checking rules u=s/c/sc if the P colony contains only sender / only consumer / both sender and consumer agents v=pas if the rules of 0L scheme are of type a→aonly, v=act if the set of rules of 0L scheme contains at least one rule of another type than a→a, w=ini if the environment or agents contain initially objects different from e, otherwise wis omitted, If a numerical parameter is unbounded, we denote it by a ∗. In [5] the authors deal with P colonies with senders and consumers with “passive” environment, they show that NEPCOL(2,3,∗, sc, pas) = N·RE. In [1] there are results of P colonies with “active” environment: NEPCOL(2,2,∗, c, act, ini) = N·RE NEPCOL(2,2,∗, sc, pas, ini)⊇N·RMpb. Other results are shown for P colonies with “passive” environment and rewriting/communication rules and with only one object inside the agent in [3] NEPCOL(1,4,∗,check, pas) = N·RE and in [5] NEPCOL(1,6,∗,no-check, pas) = N·RE. 3 P colonies with senders and consumers In this section we study computational power of P colonies with two objects inside the agent - consumer or sender. We extend the previous results reported in [1]. 156 L. Ciencialov´a, L. Cienciala, P. Sos´ık Theorem 2. NEPCOL(2,2,∗, sc, pas, ini) = N·RE. Proof. Consider register machine M= (m, H, l0, lh, P). All labels from the set H are objects in P colony. The content of register ris represented by the number of copies of objects arplaced in the environment. Let ube a mapping u:H→ {ar|1≤r≤m}∪{Li|li∈H}defined as u(li) = arfor li: (ADD(r), lj, lk) Lifor li: (SUB(r), lj, lk) We construct the P colony Π= (Σ, e, a1, aw 2, DE, B1, B2) with: −Σ={li, Li, L1 i, L2 i, W0 i, W1 i, W2 i, l0 i, l1 i|li∈H}∪{ai|1≤i≤m}∪ ∪ {e, C, Q}, −B1= (l0u(l0), P1), −B2= (ee, P2). At the beginning of computation the agent B1contains object l0representing the label of the initial instruction of M. An instruction li= (ADD(r), lj, lk) is simulated by agent B1by using following programs: B1: 1 : hli→lju(lj); arouti; 2 : hli→lku(lk); arouti; The computation is done in the following way: agent B1(sender) simulates the addition of one to the content of register r(sending one copy of object arto the environment), and it generates the object ljor lk– the label of instruction which will the simulated register machine Mexecute next. Simultaneously it “precomputes” objects for the execution of the next instruction. An instruction li: (SUB(r), lj, lk) is simulated by the following rules and programs: B1: 3 : li→W0 ie, Liout; 4 : W0 i→W1 iL1 i, e out; 5 : W1 i→W2 iL2 i, L1 iout; 6 : W2 i→l0 jl0 j, L2 iout; 7 : W2 i→l0 kl0 k, L2 iout; 8 : l0 j→l1 je, l0 jout; 9 : l0 k→l1 ke, l0 kout; 10 : l1 j→l2 je, e out; 11 : l1 k→l2 ke, e out; 12 : l2 j→l3 je, e out; 13 : l2 k→l3 ke, e out; 14 : l3 j→lju(lj), e out; 15 : l3 k→lku(lk), e out; B2: A:hee →e;Liini; B:hLie→Li;arini; C:hLiar→L1 i;L1 iini; D:hLie→L2 i;L2 iini; E:hL1 iL1 i→c;l0 jini; F:hL1 iL1 i→q;l0 kini; G:hL2 iL2 i→q;l0 jini; H:hL2 iL2 i→c;l0 kini; I:hl0 jc→c;L2 iini; J:hl0 kc→c;L1 iini; K:hL1 ic→e;e ini; L:hL2 ic→e;e ini; M:hl0 jq→q;e ini; N:hl0 kq→q;e ini; O:hqe →q;e ini; Generalized P Colonies with passive environment 157 If there are objects li(the label of SUB-instruction) and Liinside the agent B1,the agent sends object Li(using the rule labelled 3) to the environment. This is the message for the agent B2to try to consume one copy of object arfrom the environment (try to subtract one from the content of register r.) If the agent B2is successful (using the program labelled B), then the second agent consumes L1 i. If there is no arin the environment, the agent has to wait one step and then it consumes object L2 i. The agent B1generates object l0 jor l0 k,non-deterministically choosing the instruction to be simulated next (program 6 or 7). If the non-deterministic choice was wrong (the agent generates l0 jand register rwas empty or the agent generates l0 kand the register was nonempty), the agent B2would use program labelled O and the computation never halts. If the register rstores nonzero value: B1B2Env P1P2 1. liLiee ax rw3− 2. W0 ie ee Liax rw4A 3. W1 iL1 iLie ax rw5B 4. W2 iL2 iLiarL1 iax−1 rw6 or 7 C 5. l0 jl0 jL1 iL1 iL2 iax−1 rw8− 6. l1 je L1 iL1 il0 jL2 iax−1 rw10 E 7. l2 je cl0 jL2 iax−1 rw12 I 8. l3 je cL2 iax−1 rw14 L 9. lju(lj)ee ax−1 rw?− B1B2Env P1P2 1. liLiee ax rw3− 2. W0 ie ee Liax rw4A 3. W1 iL1 iLie ax rw5B 4. W2 iL2 iLiarL1 iax−1 rw7 or 6 C 5. l0 kl0 kL1 iL1 iL2 iax−1 rw9− 6. l1 ke L1 iL1 il0 kL2 iax−1 rw11 E 7. l2 ke ql0 kL2 iax−1 rw13 I 8. l3 ke qe ax−1 rw15 O 9. lku(lk)qe ax−1 rw?O If the register rstores zero: B1B2Env P1P2 1. liLiee w 3− 2. W0 ie ee Liw4A 3. W1 iL1 iLie w 5− 4. W2 iL2 iLie L1 iw6 or 7 − 5. l0 jl0 jLie L1 iL2 iw8D 6. l1 je L2 iL2 il0 jL1 iw10 G 7. l2 je ql0 jL1 iw12 M 8. l3 je qe L1 iw14 O 9. lju(lj)qe L1 iw?O B1B2Env P1P2 1. liLiee w 3− 2. W0 ie ee Liw4A 3. W1 iL1 iLie w 5− 4. W2 iL2 iLie L1 iw7 or 6 − 5. l0 kl0 kLie L2 iL1 iw9D 6. l1 ke L2 iL2 il0 kL1 iw11 H 7. l2 ke cl0 kL1 iw13 J 8. l3 ke cL1 iw15 K 9. lku(lk)ee w ?− No program is needed in P1∪P2to simulate the instruction lh:HALT. The P colony Πstarts its computation with object l0in the environment and it simulates the instruction labelled l0. By the programs it places and deletes from the environment the objects arand it halts its computation only after object lhappears in the environment. The result of computation is the number of copies of 158 L. Ciencialov´a, L. Cienciala, P. Sos´ık object a1placed in the environment at the end of computation. No other halting computation can be executed in the P colony. 4 P colonies with rewriting/communication rules In this section we deal with P colonies with passive environment and with one object inside each agent. We prove that such a P colony with three agents can generate every recursively enumerable set of natural numbers. Theorem 3. NEPCOL(1,3,∗,no-check, pas, ini) = N·RE. Proof. Let us consider register machine M= (m, H, l0, lh, P). For all labels from the set Hwe construct corresponding objects in P colony Π. The content of register rwill be represented by the number of copies of objects arplaced in the environment. We construct the P colony Π= (Σ, e, a1, d, DE, B1, B2, B3) with: −Σ={li, l0 i, l00 i, li, li, li, l1 i, l2 i, l3 i, l4 i, Mi, M1 i, M2 i, M3 i, M4 i, Ni, N1 i, N2 i, N3 i, N4 i|li∈H}∪{ai|1≤i≤m}∪{e, d, f, g}, −B1= (l0, P1), −B2= (d, P2), −B3= (e, P3). The object l0corresponds to the label of the first instruction executed by the register machine. The instruction li: (ADD(r), lj, lk) will be simulated by the agents B1and B2 by using following programs: B1: 1 : hli→l0 ii; 6 : Dl00 i→eE; 2 : hl0 i↔ei; 7 : l000 i→liv i; 3 : De→l00 iE; 8 : liv i→lv i; 4 : Dl00 i→l00 iE; 9 : hlv i→lji; 5 : Dl00 i↔l000 iE; 10 : hlv i→lki; B2: A:hd↔l0 ii; B:hl0 i→l000 ii; C:hl000 i↔ei; D:he↔l00 ii; E:hl00 i→ari; F:har↔di; The simulation of ADD-instruction starts by rewriting the object lito l0 iby the first agent. The agent B2consumes the object l0 i, changes it to l000 iand sends it to the environment. The agent B1rewrites the object eto some l00 j, for lj∈H. If this l00 jhas the same index as l000 iplaced in the environment (i.e., i=j), the computation passes to the next phase. If i6=j, the agent B1tries to generate another l00 j. When the computation gets over this checking step, agent B2generates one copy of object arand places it to the environment (adding 1 to the content of register i). Then agent B1non-deterministically chooses to generate object ljor lk. The instruction li: (SUB(r), lj, lk) is simulated by using the following rules and programs: Generalized P Colonies with passive environment 159 B1: 11 : hli→l0 ii; 15 : hl00 i→l00 ii; 19 : hliv i→Mii; 23 : hLi↔di; 12 : hl0 i↔ei; 16 : hl00 i↔l000 ii; 20 : hMi↔di; 24 : hd↔L2 ii; 13 : he→l00 ii; 17 : hl00 i→ei; 21 : hd↔Lii; 25 : hL2 i→lji; 14 : hl00 i→l00 ii; 18 : hl000 i→liv ii; 22 : hLi→Lii; 26 : hd↔L3 ii; 27 : hL3 i→lki; B2: G:hd↔l0 ii;K:hl00 i→Lii;N:har→hi;Q:hL2 i↔di; H:hl0 i→l000 ii;L:hLi↔ari;O:hh↔Lii;R:hMi→Nii; I:hl000 i↔ei;M:hLi↔Mii;P:hLi→L2 ii;S:hNi↔di; J:he↔l00 ii; B3: A0:he↔Nii;C0:hL3 i↔Lii;E0:he↔hi;G0:hy↔Mii; B0:hNi→L3 ii;D0:hLi→ei;F0:hh→yi;H0:hMi→ei; The simulation starts by generating the objects l00 i, l000 iin the same way as in the addition part described above. Then the agent B2simulates subtraction (if the subtracted register is nonzero). If there was some arin the environment, the agent generates object L2 i. This object agent B1can rewrite to lj). If the register rwas empty, the agent B2generates object Niand this object can be rewritten by agent B3to object L3 i. Finally, agent B1can rewrite object L3 ito lk.