We continue the investigation of P coloniesintroduced in [7], a class of abstract computing devices composed of independent agents, acting and evolving in a shared environment. We determine the generative power of P colonies with one resp. two objects inside each agent owing some special restrictions to the number of agents and type of programs. I{eywords: P colony, membrane systems, generative power.
P colonies were introduced in the paper [
The independent organismsliving 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 eachof them. The environment containsseveralcopiesof 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 communicationrule). 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 agentsand environment contain copiesof the environmentaiobject e.By using their programs the agents change themselves and by the environment they can affect the behavior of the other agents.In each step of the computation eachagent nondeterministically choosesone of its applicable programs and executesit. The computation halts when no agent can apply any of its programs. The result of the computation is the number of somespecificobiects prescnt at the environment at the end of the computation.
In [
In the present paper we show that restricted P colonies without checking ruies and two agents can also generateany recursively enumerableset of natural numbers working in maximally parallel way. We also show that computational power of P colonieswith one object inside the agent can simulate the partially blind register machine.
D e f i n i t i o n s Throughout the paper we assumethe reader to be familiar with the basicsof language theory.
!!-e use IVRE 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 h e n u m b e r o f o c c u r r e n c e so f t h e s y m b o l a € D r n w b y l r l " .
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 eachobject in 7 its multiplicity in IuI.The set of ail multisets with the set of objects7 is denotedby Vo. The setV' is calledthe 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 o b j e c t s V : { a t , . . e n } c a n b e r e p r e s e n t e da s a s t r i n g u o v e r a l p h a b e t V w i t h l w l o , : f @ o ) ; 1 < i S n . O b v i o u s l y ,a l l w o r d s o b t a i n e d f r o m u . 'b y p e r m u t i n g the letters can also represent .&1,and E representsthe empty multiset. trVebriefly recall the notion of P colonies.
The P colony consistsof agents and environment. Both agents and environment 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 changetheir places,so d is now inside and c is outside of the agent.
In [61the 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 insideof itself and the object d in the environment).If this rule can be executed. the agent nrust useit. If the first rule cannot be applied, the agent usesthe second one c' *-. d'. Definition
A : ( A , e ,f , V p , 8 r , . . . , B , * ) ,w h e r e - A is an alphabetof the colony, 'its elementsare called objects, - e € A i,sthe bas'icobject of tlr.ecolony, - f e A is the final objectof the colony, - V6 'isa multiset ouer A - {"}, - B r , 1 ( i 1 ' n , a r e a g e n t s ,e a c ha g e n t ' i sa c o n s t r u c tB t : ( O n , P ' ) , w h e r e . 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 f i n i t e s e t o f p r o g r a m s ,w h e r e e a c hp r o g r a m contains eractly k rules, whi,chare 'in one of the follow'ing forms: * a -+ b, th,eserules are called euolut'ionrules, * c e d, theserules are called commun'icat'ionrules, * c €+ df c' * d' , which,are called checkingrules.
An initial configurationof 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 r m a l l y ,t h e c o n f i g u r a t i o no f P c o l o n y1 1i s ( r - u 1 ,... , u n , 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 eachstep 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:
( t e | t ( r , w ) : s r : ( a - - - b ) * I1 reirsPhotr(tr('rw' )u): : 66 ' : (" *-' d) =+ r i , g h t ( r , w ) : g e r p o r t ( r , w ) : s i m p o r t ( r , w ) : 4 l i r n p o r t ( r , w ) : E ( l e f t ( r , . ) : r i ' g h t( r , w ) - E
e r n o r t( f , r i : . .
I \ i f d .e w , : ( " * - , c l l c ' - r d ' ) = + { i m p o r t ( r , . ) - d I
( : ' ' i : c ' . , \ t t , ( w a n dc,I 'e w |I i"mw p*to r t( t , r ) : d ' I For a programp and any a e {left,right, erport,i'mport},let A rranst,""f;il T).;!;il;,[fJ;
( r r , . . . , 1 1 ) n . , * d+ ditiorrs are satisfied:
anotheisrdenoteacsr @ ' t ) . . . ) w ' n , w ' n ) ,r v h e r et h e f o l l o w i n gc o n - There is a set of program labels P with lltl S n such tllat . 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 , a n d
Uo.r impo'rt(p,.u) e wn. - Furthermore, the chosen set P is maximal, that is, if an;' other program r € Ur Sr.<rlab(Pn),,f P, rs addedto P, then the conditionsaboveare 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 ) , l e t w ' , : r i g h t ( , p , * n ) u i m p o r t ( p , * n ) . I f t h e r e i s n o p € P w i t h p e l a b ( P 1 ) 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 : - p e P
A confi.gurationis halting if the set of program labels P satisfying the conditions 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 ): { l r r l , I ( r r , . . . , w n , V n ) * . ( r , , . . . , u n r r ) } , 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 , . . . , B r ) t h e m a x i m a l n u m b e r of programs associatedwith the agents in P colony I1 is called the height of P colony I/. The degreeof 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 describingthe number of the objects inside each agent.
Let us use the following notations: M c o L n a r ( 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 degreeat most n and - tlie height at most h - without using checkingrules.
If we allorvcheckingrules the family of all setsof 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 sizeof 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.
- N P C O L e , , K R ( 2 ,* , 5 ) : I r R{ E i n 1 2 , 7 1 ,
- M C O L , * , R ( 2 , * , 5 ) : I VP C O L p o , KR ( 2 ,1 ,* ) : I ' {R E i n [ + ],
- M C O L e o , ( | , * , 7 ) : I { R E i n [
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 cornputationof 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 : a r ' - B j : ( O i , P i ) , 0 1 : { " , " } , 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 generatesthe 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 (only the program 1is applicable)the systementersconfiguration(/se,ee,e). (2) For every ADD-tnstruction ly: (ADD(r),12, 13)we add programsto P1: 2 : ( e > a 7 - ; 1 1* - e ) . 4 : ( 1 1- l ' z , G* - e ) , 3 : ( e - - G ; a , * l t ) , 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 nondeterministically choosesone of t"helast two programs 4 and 5) At thc first pha^scof simrrlation of thc SU B instnrction the first agent gcncrirtes 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 this step consumesL'l or.L1 and rewrites it to 12or 13.The objects lt, 16and At the beginningof computation the first agentgeneratesthe object ls (the label of starting instruction of lvf).It generatessome copiesof object J. The agent 82 exchangethem by J'.
corrfiguration of 11 81 82 Enu e e JTC^ e e UIUf Ls J' o( t ) (2) For every ADD-instruction \: (ADD(r),Lz,ls) P1 and Pz contain: rp_.t P . . P z : 8 : \ 1 1- l ' r ) , 1 4 : ( I , * E t ) , w 9 : ( L ' t * J ' ) , 1 5 : \ L t - Q ) , 19 : (l't - Et) , 1 0 : ( L ' r - Q ) , 1 6 : ( E 1 - - l ; ) , 2 0 : ( E t * e ) , 11 : (J' * L'l) , L 7 : ( E r * l s ) , 2 1 : \ e r - L 1 ) , 12: (L'i -- L|) , 2 2 : ( L t - a , ) , 1 3 : ( L l - L r ) , 2 3 : \ a " * e ) When there is object 11inside the agent Bi, the agent rewrites it to one copy of l" and the agent sendsit to the environment. The agent 82 borrows -81 from the environment and giv,:sa 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 secondagent generatesthe symbol E'nand placesit to the environment.If this.Ll has the sameindex us E: placedin the environment, the computation can go to the next phase.If the indicesof La andEi are different, the agent 81 generatesQ and computation will never stop. If the computation gets over this checkingstep, 81 generatesobject 12or ls. (:3)For every S[/B-instruction \ : (St-lB (r) ,lz, 13) there are subsetsof programs irr P1 and -P2:
P r : 24: (11--- l'{) , 25 : (l'l *- a,) , 26: \l'i - Q) , 2 7 : \ a , - V ) ,
P t : 28 : \V ,-+li') , 29 : (l'l' --+12), 30 : \l'i' -, ls),
Noteson RestrictedP Col,nties P z : sTllf';;; 32: (l'i ---l'{'), 33 : (l'i' +* e) In the first step the first agent checksif there is any copy of.a, in t,heenvironment (whether registerr 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 .B1generatesthe object 12or 13. (4) For the halting instruction 16there are programs in bhe sets P1 and P2: By using this program, the P colony finishes computation as well as the partially blind register machine halts its computation. The last two prollrams in the sequenceof P2 are to control if the registersexcept the first one ar(f empty. if all counters ",1<'<rn d,rQempt.v configuration of 11
81 82 Enu P1 -Il 1 6 e J ' 34 or 36 2 J ' e l n 35 .ol L 6 L 6 37 TA Ln C' 37 5 L s e h 3B 6 T ; e L n "I7 n L 6
It is easy to see that tire P colony 11 correctly simulates any computation of the partially biind registermachine &1. lVe have sho'uvnthat the P colonieswith capacity k : 2 and without checking programs with height at most 2 are computationally complete. In the next part of this strrdy lvc ha,vcvcrificd that P colonics with onc ob.jcct inside thc agcnt and without checking programs can simultr,tepartially blind register machine.
Activities carried out in the field of membrane compr-rtingare currently
numerous and avzrilableat [
Tlh,swork has beensupportedby the Grant Agency of CzechRepublic Arants IVo. 201/06/0567 "Bioinformatika a biouypoity: souu'islosti,modely, aplikace" and bu IGS SU i.s2/2007.