Notes on Restricted P Colonies Lucie Ciencialovd,l and Ludek Ciencialal Institute of Computer Science, Faculty of Philosophy and Science, Silesian University in Opava, Czech Republic lucie . ciencialova@fof . s1u. cz Abstract. We continue the investigation of P colonies introduced in [7], a class of abstract computing devices composed of independent agents, acting and evolving in a shared environment. We determine the gener- ative power of P colonies with one resp. two objects inside each agent owing some special restrictions to the number of agents and type of pro- grams. I{eywords: P colony, membrane systems, generative power. Introduction P colonies were introduced in the paper [6] as formal models of a computing device inspired by membrane systems and formal grammars called colonies.This model is inspired by structure and functioning of a community of living organisms in a shared environment. The independent organisms living in a P colony are called agents.Each agent is representedby a collection of objects embedded in a membrane and rules for processingthese objects. The number of objects inside the agent is the same for each of them. The environment contains severalcopiesof the basic environmental object denoted by e.The number of the copiesof e is unlimited. With each agent a set of programs is associated. The program determines the activity of the agent. Each program consists of the same number of rules as the number of the objects inside the agent. In every moment all the objects inside of the agent are being evolved (by an evolution rule) or transported (by a communication rule). The third type of the rules is checkingrule. This type of the rules sets the priority between two communication rules. The computation starts in the initial configuration when all agents and envi- ronment contain copies of the environmentaiobject e.By using their programs the agents change themselves and by the environment they can affect the behav- ior of the other agents. In each step of the computation each agent nondetermin- istically choosesone of its applicable programs and executesit. The computation halts when no agent can apply any of its programs. The result of the computa- tion is the number of some specific obiects prescnt at the environment at the end of the computation. In [4,6,7] the authors study P colonieswith two objects inside agents.In this case programs consist of two rules. If the former of these rules is evolution and 180 L. Ciencialova and L. Cienciala the latter is communication or checking,w€ talk about restricted.P colonies.If we allow also another combination of the types of the rules, we obtain non-restricted P colonies.The restricted P ccionieswith the checkingrules are computationaily c o m p l e te [3 ,4 ]. In the present paper we show that restricted P colonies without checking ruies and two agents can also generate any recursively enumerable set of natural numbers working in maximally parallel way. We also show that computational power of P colonies with one object inside the agent can simulate the partially blind register machine. Definitions Throughout the paper we assumethe reader to be familiar with the basicsof lan- guage theory. !!-e use IV RE to denote the family of recursively enumerable sets of natural numbers. Let D be the alphabet. Let E* be the set of all words over I (including the empty rvord e). We denote the length of the word u € D" by lull and t he n u m b e r o f o c c u rre n c e so f th e symbol a € D rn w by l rl " . A multiset of objects &1 is a pair IuI(V,/), where I/ is an arbitrary (not necessarilyfinite) set of objects arrd / is a mapping,f : V ---,I{; f assigns to each object in 7 its multiplicity in IuI.The set of ail multisets with the set of objects 7 is denotedby Vo. The set V' is called the support of fuI and d.enotedby supp(tul) if for all r € \-' f (r) 10. The cardinality of IuI, d.enotedby card,(fu|), is defined by card(IuI) : Loev f @). Any multiset of objects .0,/with the set of obj e c ts V : { a t,. .e n } c a n b e r epresentedas a stri ng u over al phabet V w i th lwlo ,: f @ o ); 1 < i S n . O b v i ousl y,al l w ords obtai ned from u.' by permuti ng the letters can also represent .&1,and E representsthe empty multiset. 2. ! P Colony trVebriefly recall the notion of P colonies. The P colony consists of agents and environment. Both agents and environ- ment contain objects. With every agent the set of progranr is associated.There are two kinds of rules in programs. The first type called evolution is in tire form a --' b. It means that object a inside of agent is rewritten (evolved)to object b. The second type of rules can be called communication and they are in the form c ''-' d. When this rule is performed, the object c inside and the object r/ outsicle of the agent change their places, so d is now inside and c is outside of the agent. In [61 the ability of agents is extender] by checking programs. They give to the agents the opportunity to opt between two possibilities.These rules have fbrm c *' d/c' *-, d' . If the checking rule is performed.,the communication rule c *-- d has higher prioritv to be executed as the rule c' *-- d,'. It means that the agent chccks the possibility of using the rule c r-, d, (it tries to find ob.ject c inside of itself and the object d in the environment). If this rule can be executed. the agent nrust use it. If the first rule cannot be applied, the agent usesthe second one c' *-. d'. Notes on RestrictedP Colonies l8l Definition 1. The P colonA of the capac'ityk is a construct A : ( A , e ,f , V p , 8 r , . . . , B , * ) ,w h e r e - A is an alphabet of the colony, 'its elements are called objects, - e € A i,s the bas'icobject of tlr.ecolony, - f e A is the final object of the colony, - V6 'isa multiset ouer A - {"}, - Br, 1 ( i 1 ' n , a re a g e n ts ,e achagent' i s a constructB t: (On,P ' ), w here . Oi is a multiset ouer A, it deterrnines the znit'ial state (content) of the a g e n t ,l O r l : k , . P r - { p o ,r,.. . ,p i ,k i } i s a fi ni te set of programs, w here each program contains eractly k rules, whi,chare 'in one of the follow'ing forms: * a -+ b, th,eserules are called euolut'ionrules, * c e d, these rules are called commun'icat'ionrules, * c €+ df c' * d' , which,are called checking rules. An initial configuration of the P colony is (n * 1)-tuple of strings of objects present in the P colony at the beginning of the computation, it is given by Oi for I S i ,S n a n d 7 6 . F o rm a l l y ,th e confi gurati onof P col ony11 i s (r-u1,. . .,un,w n), where lrrl : k, 1 < i I n, uri representsall the objects placed inside the i-th agent and up € @- {r}). representsall the objects in the environment different from e. The computation can be done in two different ways in a parallel and in a seqrrentialway. At each step of the parallel computation each agent tries to find one program to use. If the number of applicable programs is higher than one, the agent nondeterministically choosesone of them. At one step of computation the maximal number of agents works. On the other hand at each step of sequential computation only one agent can use its program. Let the programs of each P1 be labeied in a one-to-one manner by labels in a s e t l a b ( P 1 )i n s u c ha w a y t h a t l o b ( 4 ) n l a b ( P i ) : A f o r i t ' j , , I < i , j 1 n . For a rule r and a muitiset u e V" we can define: ( te|t (r,w) : s risht(r'w) : 6 ri,ght(r,w): g r : (a--- b) * I ' : (" *-' d) =+ : 6 erport(r,w) : s 1 erPort(r' u) lirnport (r,w) : E i mport (r,w ) : 4 ( l e f t ( r , . ) : r i ' g h t( r , w ) - E ernort(f,ri : .. \ I if d.e w , : ( " * - ,c l l c ' - r d ' ) = +{ i m p o r t ( r , . ) - d I (:''i : c'.,\tt, "w*t (t, r) : d' | import ( w and, cI'e w I I For a programp and any a e {left,right, erport,i'mport},let A rranst,""f;il T).;!;il;,[fJ; is denotecr another as ( r r , . . . , 1 1 ) n . , * d+ @ ' t ) . . . ) w ' n , w ' n ) ,r v h e r et h e f o l l o w i n gc o n - ditiorrs are satisfied: - There is a set of program labels P with lltl S n such tllat 182 L. Ciencialova and L. Cienciala . p , p ' e P , p * p ' , p € l a b ( P i ) i m p l i e sp ' ( l a b ( P i ) , o f o r e a c hp € P , p e L a b ( P i ) ,l e f t ( p , - " ) U e r p o r t ( p , - " ) : u)j, and U o .r i mp o ' rt (p ,.u ) e w n. - Furthermore, the chosen set P is maximal, that is, if an;' other program r € U r Sr.< rl a b (Pn ),,f P , rs added to P , then the condi ti onsabove are not satisfied. N o w , f o r e a c hj , L < j S n , f o r w h i c h t h e r e e x i s t sa p € P w i t h p € l a b ( P i ) , let w', : right(,p,*n)uimport(p,*n). If thereis no p € P with p e lab(P1) for some j, t < j { n, then let ,'j : ?rr;and moreover, let u'E : wB - l) impo'rt (p,up) u N erport (p,,ra) ' r:- peP A confi.guration is halting if the set of program labels P satisfying the con- ditions above cannot be chosento be other than the empty set. With a halting computation we can associatea result of the computation. It is the number of copies of the special symbol / present in the environment. The set of numbers computed by a P colony' 11 is defined as A - ( 1 1 ): ( r r , . . . , w n , V n )* . ( r , , . . . , u n r r ) } , {lrrl, I w h e r e ( r , , . . . , u n , V n ) i s t i r e i r r i t i a lc o n f i g u r a t i o n(,u 1 , . . . , u n , u a ) i s a h a l t i n g configuration, and =+* denotes the reflexive and trl,nsitive closure of =+. Becauseof nondeterminism in a computation of the P colony, we can obtain more tha.n one halting computation. Hence what we associatewith P colony 11 is a set of natural numbers denoted by ,n/(il ) computed by all possible haiting computations of 11. G i v e n a P c o l o n yI I : ( A , e ) f , V o , 8 r , . . . , Br) the maximal number of programs associated with the agents in P colony I1 is called the height of P colony I/. The degree of P colony II is the number of agents in P colofty n. The third parameter characterizing a P colony is the capacity of P colorry n describing the number of the objects inside each agent. Let us use the following notations: McoLnar(k,n,h) - t h e f a m i l y o f a l l s e t s o f n u m b e r sA * ( / 7 ) c o m p u t e d b y P coloniesworking in parallel way with: - the capacity k, - the degree at most n and - tlie height at most h - without using checkingrules. If we allorv checkingrules the family of all sets of numbers computed by P colonies is derroied by !{PC'OLparK.If the P colonies are restricted too, we change notation to !{ PCOLT',R or I{ PCOL,',K R. 2.2 Register Machines In this work we want to characterizethe size of the larniliesi{PCOLpo,(k,'n,h) comparing them rvith the recursively enumerable sets of numbers. To achieve this aim we need the notion of a register machine. Notes on RestrictedP Colonies 183 Definition 2. [S] A register mach'ine i,s tlte construct M : (*,H,ls,lh,P) wh,ere: - m 'is the number of registers, - H is the set of instruct'ion labels, - ls i,s the initi,al/start label, 16 i,s the final Label, - P is a finite set of instructions i,njectiuelylabeledwith the elements from the giuen set H. The instruction of the register machine are of the following forms: ly : (AD D (r),l z ,1 3 ) A d d 1 to th e contentsof the regi sterr and proceedto the instruction (labeledwith) 12or 13. \: (SU B(r),l r,1 3 ) If th e re g i sterr i s not empty, then subtract l from i ts con- tents and go to instruction 12,otherwiseproceedto instruc- ti o n 1 3 . 1 6 :H A L T Stop the machine. The final label ln is only assignedto this lnstructron. Without loss of generality, one can assume that in each ADD-instruction l y : ( A ( r ) , l z , l z ) a n d i n e a c h S U B - i n s t r u c t i o n1 1: ( 5 ( r ) , l z , l s ) t h e i a b e l s\ , 1 2 , 1 3 are mutually distinct. The register machine fuI computes a set ,^/(/l/) of numbers in the following way: we start with ail registers empty (hence storing the number zero) with the instruction with label ls and 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 M and hence it is introduced in .n/(&/). (Because of the nondeterminism in choosing the continuation of the computation in the case of ADD-instructions, N(M) can be an infinite set.) It is knorvn (see e.g [7]) that in this way we can compute all sets of numbers which are Turing computable. ivloreover,'ivecail a register machine partiaily lrlind [5], if we interpret a sub- t r a c t i n s tru c ti o n i n th e fo l l o w i ng w ay: \: (S (r' );l z;l z) - i f regi ster r i s not empty, then subtract one from its contents and go t,oinstruction 12or to instruc- tion 13;if register r is empty when attempting to tlecrement register r, then the program ends without yielding a result. When the register rnachine reachesthe final stirte, the result obtained in the first register is only taken into account if the rernaining registers are empty. The family of sets of non-negative integers generat,e'dby partially blind register machines is denoted by N RIuIpa.The partially blind register machine accepts a proper subset of .n/ftE. 3 On computational power of restricted P colonies Without Checking The next resultswereprovedto be true: - N PCOLe,,K R(2,*,5) : Ir{RE in 12,71, - M C O L , * , R ( 2 , * , 5 ) : I VP C O L p o , KR ( 2 ,1 ,* ) : I ' {R E i n [ + ], - MCOLeo,(|,*,7): I{RE in [1], - NPCOLeo,(L,4,*) - I/R.O in 11], r84 L. Ciencialova and L. Cienciala 3 . 1 P colonies With Two Objects T h e o r e m 1 . l VP C O L p o , R ( 2 , 2 . x ) : ^ l R E . Proof. Let us consider a register macliine ,4,1rvith rn registers. W-e construct a P colony II : (A,", f ,V", Bt, Bz) sinrulatinga cornputation of registermacirine r U w i t h : - A : { G } U { L r , L ' o , l ' o ' , 1 ' r " , 1 ' ; " ' , h , hL,rL, rL.'!ii,,L ' i ' ,F r I l o € H } l ) U {o'" I I < r < m}, -f: ar' - Bj : (Oi,Pi), 01 : {","},j:L,2 At the beginning of thc computation thc first agcnt gencratesthe ob.jcctls (the Iabel of starting instruction of ,&1).Then it starts to simulate instruction labeled ls and generates the label of tire next instruction. The sets of programs are as follows: (1) For initializing of the simulation there is one program in P1: L : \ e - - +L o i e? + e ) The initial configurationof I/ is (ee,ee,e). After the first step of computation ( o n l y th e p ro g ra m 1 i s a p p l i c a bl e)the system entersconfi gurati on(/se,ee,e). (2 ) F o r e v e ry A D D -tn s tru c t i on l y: (A D D (r),12, 13)w e add programsto P 1: 2 : ( e > a 7 - ; 1 1* - e ) . 4 : ( 1 1- l ' z , G* - e ) , 3: (e -- G;a, * lt), 5 : (11 --+le)G *-, e) lVhen there is object 11inside the agent, it generatesone copy of a,, puts it to the environment and generatesthe label of the next instruction (it nondetermin- istically choosesone of t"helast two programs 4 and 5) configuration of 11 Br 82 Enu P1 P^ 1 Ite ee ai 2 o a r€ ee l pf, , t) ;.) G h ee of+ | 4or5 r! lze ee of*t G (3 ) F o r e v e ry SU l 3 -i n s tru c t i on11: IS LIB (r),l z,13) there are subsetsof pro- granls in Pt and P2: Programs in Pr Programs in Pr Programs in P2 At thc first pha^scof simrrlation of thc SU B instnrction the first agent gcncr- irtes r-ibject l\, whicii is consunred bv the sccond agcnt. The agent 82 generates sv-mbol 11 and tries to consurle one copy of symllr.rl or. If there is any a,., the agent sends to the e'nvironment object L'l and consltrnes I1. The first agent afber Notes on Restricted P Colonies 185 this step consumesL'l or.L1 and rewrites it to 12 or 13.The objects lt, 16and l,; ur. for a synchronization of the computation in both agents and for storing informations about the state of the computation. An instruction 11 : (SUB(r),lz,ls) is simulated by the following sequence of steps. If the register r is empty: If the register r is not empty: configuration of 11 configuration of I/ 81 82 Enu P1 Pz 81 82 Enu P1 Pz 1 Ite ee atr o Lf ee 6 2 L'r" ee af 7 (r" ee 7 3 l'i" ee l\"f 818 li" ee l'r B18 = A l'l'" LJ\ l'i"f 919 l'L'" LJI I'i 919 5 l'1" L\l'{ Lpf 10 20 (1" L'tl'i Lr 10 " " 6 ie L'lo, L1L'1af;-l i 1 2 l ie L\I'i Ly 11 : : 7I he eLt L'laf-r L2 22 If L\t'i L1 13 8 lzL'i ee al-I 1A I I tzLt L\ti 15 9 Lze ee a f ; - rl z Fse L'tl'i lJ 16 L\t'{ J?3 17 23 W Ise Fse 2or6 24 bf; or none ?? ee lsL't ( ) For the halting instruction 17,there is no program neither in the set P1 either in the set P2. It is easy to see that the P colony 11 correctly simulates any computation of the register machine IUI and the number contained on the first register of fuI correspondsto the number of copiesof the object o1 pr€s€rted in the environment of II. The rest of the proof follows by the Church-Turing thesis and by the computational universality of the register machine. n 3.2 P Colonies With One Object Theorem 2. MCOL,,',R(I,2,*) 1 I{RIuIea. Proof. Let us consider a register machine /l,/ with m registers. \Are construct a P c o l o n y I I : ( A , e , f , V p , B t , B z ) s i m u l a t i n ga c o m p u t a t i o nof the register machine .4,/with: - A - { J , J ' , V , Q } U { l n ,l i , I ' r ' , L t , L ' r , L ' n ' , E n l l t e H } U {o, | 1 Sr/-mj, -f:at, - B t : ( O r ,P r ) , O i : { " } , 1 : I , 2 The sets of programs are as follows: (1) For initializing the simulation: Pt: Pr: Pz: 5l-G --T; 2: (J<-el , 4: (Q-Q), 6 7: (J'**e) 186 L. Ciencialova and L. Cienciala At the beginning of computation the first agent generatesthe object ls (the label of starting instruction of lvf).It generatessome copies of object J. The agent 82 exchangethem by J'. corrfiguration of 11 81 82 Enu ee I T^ JC 2or3 ee 1 If UU 2or3 6 Ls J' 8or24or34 7 o( t ) (2) For every A D D -i n s tru c ti o n \: (A D D (r),Lz,l s) P 1 and P z contai n: p. r_t P.. Pz: 8 : \ 1 1- l ' r ) , 9: (L't*J'), 14: (I, * Et) , 15: \Lt-Q), w 19 : (l't - Et) , 10: (L'r-Q), 16: (E1-- l;) , 20: (Et * e), 11 : (J' * L'l) , L7: (Er*ls) , 21: \er-L1), 12: (L'i -- L|) , 22: (Lt - a,) , 13: (Ll-Lr), 23: \a" * e) When there is object 11 inside the agent Bi, the agent rewrites it to one copy of l" and the agent sends it to the environment. The agent 82 borrows -81 from the environment and giv,:s a little altered (to .ei) back. The agent 81 r€rA'ritesthe object J' to some L;. We have to generate it in three steps to wait till the second agent generatesthe symbol E'nand places it to the environment. If this.Ll has the same index us E: placed in the environment, the computation can go to the next phase.If the indices of La and Ei are different, the agent 81 generatesQ and computation will never stop. If the computation gets over this checkingstep, 81 generatesobject 12or ls. configuration of // Br 82 Enu P1 P2 l. lre Il 8 2. I'r e J, 9or10 3. JC ,l l1 11 18 l f tt Il +. "l " i t2 19 5. L', E1 13 20 o. r^ LTE Ltl 74 or L5 7. E1 e r- u\ 16 or LT 2l lr 8. L2 tI 8or24or34 22 .) 9. ! (1, 9 or 25 o'r 35 23 10. ,t P aT (:3)For every S[/B-instruction \ : (St-lB (r) ,lz, 13) there are subsetsof programs irr P1 and -P2: Notes on RestrictedP Col,nties 187 Pr: Pt: Pz: 24: (11--- l'{) , 28 : \V ,-+li') , sTllf';;; 25 : (l'l *- a,) , 29 : (l'l' --+12), 32: (l'i ---l'{') , 26: \l'i - Q) , 30 : \l'i' -, ls) , 33 : (l'i' +* e) 27: \a,-V), In the first step the first agent checksif there is any copy of.a, in t,he environ- ment (whether register r is not empty). In the positive caseit rewrites a, toV, in the other case l'1 is rewritten to Q and the computation will ncver halt. At the end of this simulation the agent .B1 generatesthe object 12or 13. configuration of I/ configuration of 11 81 82 Enu P1 P2 81 82 Enu 1 01 ar 24 1 11 e 2 ul i l1 a.r 25 or 26 2 t'{ e 3 ar e lll Ly 27 31 3 Ae a A V Itl !1 32 4 Ae ^ V lilt bl 33 6 V e lttl L1 28 7 lilt 01 29 or 30 8 lz (4) For the halting instruction 16 there are programs in bhe sets P1 and P2: Pt: Pz: Pz: W 39 : (e *.17) , 43: \Ln * a,) , l