Homogenn´ı P kolonie1 Ludˇ ek Cienciala1 , Lucie Ciencialov´ a1 , Alica Kelemenov´ a1,2 1´
Ustav informatiky, Slezsk´a univerzita Opava Bezruˇcovo n´am.13, 746 01 Opava
2
Katedra informatiky, Katolick´a univerzita Ruˇzomberok, N´ amestie A. Hlinku 56/1, 034 01 Ruˇzomberok, Slovensk´a republika
[email protected],
[email protected],
[email protected]
Abstrakt
pˇred´av´an´ı informac´ı mezi agenty, kdy jeden agent vylouˇc´ı do prostˇred´ı urˇcitou l´atku odpov´ıdaj´ıc´ı jeho stavu v dan´e situaci. Napˇr´ıklad u mravenc˚ u patˇr´ı mezi nejd˚ uleˇzitejˇs´ı komunikaˇcn´ı prvek mravenˇc´ı pachy, tzv. feromony. Mezi v´ yhody vyuˇz´ıv´an´ı pach˚ u patˇr´ı to, ˇze mravenc˚ um staˇc´ı i mal´ y mozeˇcek k vytvoˇren´ı pomˇernˇe sloˇzit´e spoleˇcensk´e struktury. Existuj´ı vˇsak parazit´e, kteˇr´ı jsou schopni napodobit mravenˇc´ı pach a z toho vypl´ yv´a snadn´a napadnutelnost dan´eho syst´emu. Mezi ˇcast´ ymi parazity mravenc˚ u jsou mravenci jin´eho druhu. Nyn´ı se pod´ıvejme ˇ na druh´ y pˇr´ıklad a to vˇcely. Zihadlov´ y apar´at vˇcely tvoˇr´ı nˇekolik ˇzl´az. V jejich v´ ymˇeˇsc´ıch je histamin, fosfolip´aza a hyaluronid´aza vyvol´avaj´ıc´ı nepˇr´ıjemn´e pocity svˇedˇen´ı a p´alen´ı v okol´ı vpichu. Tyto ˇzl´azy tak´e vyluˇcuj´ı i feromony, kter´e slouˇz´ı k vyvol´an´ı poplachu u ostatn´ıch vˇcel. Do r´any vstˇrikuj´ı vˇcely i l´atku pˇripom´ınaj´ıc´ı v˚ uni ban´an˚ u. Pomoc´ı n´ı se orientuj´ı dalˇs´ı vˇcely a vpichuj´ı dalˇs´ı ˇzihadla do bl´ızkosti prvn´ıho, tzn. u kaˇzd´e d´avky jedu je i d´avka izoamylacet´atu. Izoamylacet´at je st´al´a l´atka informuj´ıc´ı nˇeco okolo 10 minut dalˇs´ı vˇcely, kde se nach´az´ı ”nepˇr´ıtel”. Vˇcely z jednoho u ´lu se pozn´aj´ı podle specifick´e v˚ unˇe, podobn´e u ´lov´e v˚ uni, kter´a sest´av´a z mnoha sloˇzek. Vˇcely jsou schopny se vyznat i ve smˇesici pach˚ u. Pyl a nektar dvou u ´l˚ u nevon´ıv´a stejnˇe, z d˚ uvodu, ˇze b´ yv´a sb´ır´an jednak z r˚ uzn´ ych rostlin, ale hlavnˇe v r˚ uzn´em pomˇeru tˇechto rostlin. Povrch tˇela vˇcely je uzp˚ usoben tak, ˇze nab´ır´a v˚ uni u ´lu a udrˇzuje si ji. Ale to jeˇstˇe nen´ı vˇsechno. Vˇcely si znaˇc´ı cestu k nektaru. Jsou to molekuly neralu, citralu a geraniolu, jejichˇz v˚ unˇe dohromady pˇripom´ın´a v˚ uni kvˇet˚ u meduˇ nky nebo plod˚ u kdoule. Pom´ahaj´ı vˇcel´am naj´ıt i cestu zp´atky do u ´lu. Pro orientaci slouˇz´ı vˇcel´am i tance uvnitˇr u ´lu a mnoho dalˇs´ıch v˚ un´ı. Napˇr. terpeny, aldehydy, ketony i dalˇs´ı ˇstiplav´e a aromatick´e slouˇceniny v r˚ uzn´ ych mnoˇzstv´ıch ovlivˇ nuj´ı dorozum´ıv´an´ı vˇcel a umoˇzn ˇuj´ı fungov´an´ı vˇcelstva. V˚ uni vˇcely pouˇz´ıvaj´ı
V pˇr´ıspˇevku prezentujeme v´ ysledky z´ıskan´e pˇri v´ yzkumu P koloni´ı, jedn´e z variant v´ ypoˇcetn´ıch model˚ u zaloˇzen´ ych na nez´ avisl´ ych membr´ anov´ ych agentech, kter´e se vyv´ıj´ı a p˚ usob´ı ve spoleˇcn´em prostˇred´ı. Budeme se zab´ yvat pˇredevˇs´ım P koloniemi, kter´e jsou homogenn´ı vzhledem k typu pravidel jednotliv´ ych program˚ u agent˚ u. Poˇcet agent˚ u, stejnˇe jako poˇcet program˚ u v kaˇzd´em agentu lze omezit i pˇri zachov´ an´ı v´ ypoˇcetn´ı u ´plnosti homogenn´ıch P koloni´ı. Uvedeme v´ ysledky pro P kolonie s jedn´ım a se dvˇema objekty uvnitˇr kaˇzd´eho agenta.
1
´ Uvod
P kolonie byly zavedeny v pr´ aci [8] jako jeden z model˚ u inspirovan´ ych membr´ anov´ ymi syst´emy ([10]) a gramatick´ ymi syst´emy, kter´e naz´ yv´ ame kolonie ([6]). Dan´ y model je inspirov´ an strukturou a ˇcinnost´ı ˇziv´ ych organism˚ u ve spoleˇcn´em prostˇred´ı. Autonomn´ı organismy ˇzij´ıc´ı v P kolonii naz´ yv´ame agenty. Jako agenty si m˚ uˇzeme klidnˇe pˇredstavit napˇr´ıklad mravence nebo vˇcely. Samozˇrejmˇe nebudeme zkoumat jejich stavbu nebo ˇzivotn´ı projevy do detail˚ u a hledat adekv´ atn´ı popis, formalismus v dan´em modelu. Agenty i jejich ˇzivotn´ı projevy jsou definov´any velmi jednoduch´ ym zp˚ usobem. Kaˇzd´ y agent je tvoˇren jednou membr´ anou ohraˇ niˇcuj´ıc´ı oblast s objekty. Poˇcet objekt˚ u uvnitˇr agenta je pevnˇe stanoven a je pro vˇsechny agenty stejn´ y. Poˇcet objekt˚ u uvnitˇr kaˇzd´eho agenta urˇcuje tzv. kapacita P kolonie. Objekty P koloni´ı si m˚ uˇzeme pˇredstavit v pˇr´ırodˇe jako l´atky, kter´e jsou schopny dan´e organismy mˇenit, pˇrij´ımat, vyluˇcovat do prostˇred´ı. I takto jednoduch´e ˇzivotn´ı projevy mohou emergovat v mnohem sloˇzitˇejˇs´ı ˇzivotn´ı projevy cel´e P kolonie. Nejv´ıce k tomu pˇrisp´ıv´a
1 Podˇ ˇ 201/06/0567, v´ ekov´ an´ı V´ yzkum byl proveden za podpory grantu GACR yzkumn´ eho z´ amˇ eru MSM 4781305903 a grantu OP RLZ CZ 04.1.03/3.2.15.2/0295.
71
jako dorozum´ıvac´ı jazyk. Prostˇred´ı P kolonie slouˇz´ı jako komunikaˇcn´ı kan´ al, pr´ avˇe pˇres prostˇred´ı agenty jsou schopni ovlivˇ novat chov´ an´ı ostatn´ıch agent˚ u. Stejnˇe jako mravenci a vˇcely. V prostˇred´ı se nach´azej´ı speci´aln´ı objekty, kter´e naz´ yv´ ame enviroment´aln´ı a oznaˇcujeme e. Poˇcet objekt˚ u e je v prostˇred´ı obecnˇe nekoneˇcnˇe mnoho. ˇ Cinnost agenta je urˇcena pomoc´ı program˚ u. Kaˇzd´ y agent m´a k dispozici svou mnoˇzinu program˚ u. Program je tvoˇren pravidly a to pravidly pˇrepisuj´ıc´ımi, komunikaˇcn´ımi a kontroln´ımi. Kontroln´ı pravidla jsou rozˇs´ıˇren´ım pravidel komunikaˇcn´ıch. Kaˇzd´ y program obsahuje tolik pravidel, kolik je objekt˚ u uvnitˇr agenta. V kaˇzd´em okamˇziku jsou vˇsechny objekt uvnitˇr agenta zmˇenˇeny a nebo pˇresunuty.
sah a pomoc´ı prostˇred´ı mohou ovlivˇ novat chov´an´ı ostatn´ıch agent˚ u v dalˇs´ım kroku v´ ypoˇctu. V pˇr´ırodˇe se tak´e ˇcasto prostˇred´ı vyuˇz´ıv´a jako komunikaˇcn´ı kan´al. Nˇekter´e organismy vyluˇcuj´ı jist´e l´atky do prostˇred´ı a t´ım ovlivˇ nuj´ı chov´an´ı ostatn´ıch. V´ ypoˇcet je paraleln´ı. V kaˇzd´em kroku v´ ypoˇctu kaˇzd´ y agent nedeterministicky vybere jeden ze sv´ ych aplikovateln´ ych program˚ u a vykon´a jej. V´ ypoˇcet konˇc´ı zastaven´ım, kdy ˇz´adn´ y agent nem˚ uˇze aplikovat ˇz´adn´ y ze sv´ ych program˚ u. V´ ysledkem v´ ypoˇctu je poˇcet urˇcit´ ych objekt˚ u v prostˇred´ı na konci v´ ypoˇctu. P kolonie jsou v´ ypoˇcetnˇe u ´pln´e. Zajimav´a je ot´azka, jak´ y je nejmenˇs´ı poˇcet agent˚ u, poˇcet program˚ u v agentu pˇri zachov´an´ı v´ ypoˇcetn´ı u ´plnosti. V tomto pˇr´ıspˇevku popisujeme vlastnosti homogenn´ıch P koloni´ı , to znamen´a P koloni´ı s programy tvoˇren´ ych stejn´ ym typem pravidel (pˇrepisuj´ıc´ımi, komunikaˇcn´ımi nebo kontroln´ımi) pro vˇsechy objekty uvnitˇr agenta. Kaˇzd´a P kolonie s kapacitou jedna je homogenn´ı. Homogenn´ı P kolonie byly poprv´e studov´any v [1]. Budeme se zab´ yvat poˇctem agent˚ u a poˇctem program˚ u v agentech pˇri zachov´an´ı v´ ypoˇcetn´ı u ´plnosti homogenn´ıch P koloni´ı s kapacitou jedna a dvˇe. To znamen´a, ˇze vˇsechny agenty bude v prvn´ım pˇr´ıpadˇe obsahovat jeden objekt a ve druh´em pˇr´ıpadˇe dva objekty. V n´asleduj´ıc´ı kapitole uvedeme z´akladn´ı definice, definici P kolonie a definici registrov´eho stroje, kter´ y je pouˇzit v d˚ ukazech v´ ypoˇcetn´ı s´ıly P koloni´ı. V tˇret´ı kapitole se budeme zab´ yvat P koloniemi s jedn´ım objektem uvnitˇr kaˇzd´eho agenta. V [1] jsme uk´azali, ˇze v nejlepˇs´ım pˇr´ıpadˇe sedm program˚ u u kaˇzd´eho agenta, stejnˇe tak i pˇet agent˚ u zabezpeˇcuje v´ ypoˇcetn´ı u ´plnost P koloni´ı. V ˇcl´anku uk´aˇzeme, ˇze ˇsest program˚ u v kaˇzd´em agentu bez omezen´ı poˇctu agent˚ u je v´ ypoˇcetnˇe u ´pln´ y. V´ ysledky t´ ykaj´ıc´ı se homogenn´ıch P koloni´ı se dvˇema agenty v kaˇzd´em agentu uvedeme v kapitole 4. Dva objekty v agentech dovoluj´ı maxim´alnˇe sn´ıˇzit poˇcet agent˚ u tak, ˇze v´ ypoˇcetn´ı u ´plnost m˚ uˇze b´ yt realizov´ana pouze jedn´ım agentem. Nav´ıc ˇctyˇri programy v kaˇzd´em agentu dovoluj´ı generovat kaˇzdou spoˇcitatelnou podmnoˇzinu pˇrirozen´ ych ˇc´ısel (bez omezen´ı poˇctu agent˚ u).
Existuj´ı tˇri z´ akladn´ı typy pravidel: (1) Pˇrepisuj´ıc´ı pravidla maj´ı tvar a → b. Aplikac´ı pravidla je objekt a v agentu pˇreps´ an na objekt b. (2) Komunikaˇcn´ı pravidla maj´ı tvar c ↔ d. Pomoc´ı tohoto pravidla je objekt c, kter´ y je uvnitˇr agenta, pˇresunut ven a objekt d, kter´ y je vnˇe, je pak pˇresunut dovnitˇr agenta. Schopnosti agent˚ u jsou rozˇs´ıˇreny o (3) kontroln´ı programy. D´ ame jimi agent˚ um moˇznost v´ ybˇeru mezi dvˇema moˇznostmi. Programy maj´ı tvar ha → b, c ↔ d/c0 ↔ d0 i. Pokud tento program je aplikov´an, pravidlo c ↔ d m´ a vyˇsˇs´ı prioritu k proveden´ı neˇz pravidlo c0 ↔ d0 . To znamen´ a, ˇze agent vybere pravidlo c ↔ d (pokouˇs´ı se naj´ıt uvnitˇr objekt c a objekt d v prostˇred´ı). Pokud toto pravidlo m˚ uˇze b´ yt vykon´ ano, tak je pouˇzito. Kdyˇz prvn´ı pravidlo nem˚ uˇze b´ yt provedeno, agent pouˇzije druh´e pravidlo z dan´e dvojice pravidel c0 ↔ d0 . Pro pˇr´ıpad dvou objekt˚ u uvnitˇr agenta, m˚ uˇzeme pˇrepsat kontroln´ı pravidlo do tvaru c ↔ d/c ↔ d0 . Pokusme se tato pravidla, alespoˇ n z ˇc´ asti interpretovat v pˇr´ırodˇe. Pˇrepisuj´ıc´ı pravidla zabezpeˇcuj´ı zmˇenu l´ atky a uvnitˇr organismu na jinou l´ atku b. Komunikaˇcn´ı pravidla, jsou pr´avˇe ta pravidla, pomoc´ı kter´ ych urˇcit´e organismy komunikuj´ı. Jedn´ a l´ atka c je vylouˇcena do prostˇred´ı a dalˇs´ı l´ atka d, je pˇrijata organismem. L´atku d m˚ uˇzeme klidnˇe v nˇekter´ ych pˇr´ıpadech ch´ apat jako zpˇetnou vazbu pˇri vylouˇcen´ı l´ atky c. U kontroln´ıch pravidel organismus zjiˇst’uje, jestli se v prostˇred´ı vyskytuje urˇcit´ y typ l´ atky, pokud ne, pˇrizp˚ usob´ı sv´e chov´an´ı tomuto nedostatku. To znamen´ a napˇr´ıklad mravenec pokud nenajde, ztrat´ı feromonovou stopu, bude ji d´ale hledat a pokud ji najde, bude ji sledovat.
2
V´ ypoˇcet zaˇc´ın´ a v poˇc´ ateˇcn´ı konfiguraci, kter´a je definov´ana n´ asleduj´ıc´ım zp˚ usobem: prostˇred´ı a vˇsechny agenty obsahuj´ı pouze kopie objekt˚ u e. Aplikov´an´ım program˚ u agenty mohou mˇenit sv˚ uj ob-
Definice
Budeme pˇredpokl´adat, ˇze ˇcten´aˇri jsou zn´amy z´akladn´ı definice a poznatky z teorie form´aln´ıch jazyk˚ u a automat˚ u. V´ıce informac´ı o membr´anov´ ych v´ ypoˇctech je moˇzno z´ıskat v [11], o v´ ypoˇcetn´ıch stroj´ıch a koloni´ıch
72
hou b´ yt modifikov´any na tvar hab → cdi. Stejn´ ym zp˚ usobem m˚ uˇzeme modifikovat komunikaˇcn´ı programy na tvar hab ↔ cdi.
ˇc´asteˇcnˇe v [9] a [6, 7, 8]. Poˇcet ˇcl´ ank˚ u o dan´em modelu neust´ale roste, nejl´epe se o tom m˚ uˇzeme pˇresvˇedˇcit na webov´ ych str´ank´ ach [12]. Uvedeme zde oznaˇcen´ı pouˇzit´e v tomto ˇcl´ anku. NRE budeme oznaˇcovat mnoˇziny rekurz´ıvnˇe spoˇcitateln´ ych nez´ aporn´ ych cel´ ych ˇc´ısel a N mnoˇzinu nez´aporn´ ych cel´ ych ˇc´ısel. Σ je oznaˇcen´ı pro abecedu. Necht’ Σ∗ je mnoˇzina vˇsech slov nad abecedou Σ (vˇcetnˇe pr´ azdn´eho slova ε). Pro d´elku slova w ∈ Σ∗ budeme pouˇz´ıvat oznaˇcen´ı |w| a pro poˇcet v´ yskyt˚ u symbol˚ u a ∈ Σ ve w |w|a . Multimnoˇzina objekt˚ u M je dvojice M = (V, f ), kde V je libovoln´ a (ne nutnˇe koneˇcn´ a) mnoˇzina objekt˚ u a f je zobrazen´ı f : V → N ; f pˇriˇrazuje kaˇzd´emu objektu z V jeho n´ asobnost v M . V ◦ je mnoˇzina vˇsech koneˇcn´ ych multimnoˇzin nad koneˇcnou mnoˇzinou V . Support mnoˇziny M je mnoˇzina supp(M ) = {a ∈ V | fM (a) 6= 0}. Kardinalitu mnoˇ ana jako P ziny M znaˇc´ıme |M | a je definov´ |M | = a∈V fM (a). Koneˇcn´ a multimnoˇzina M nad V m˚ uˇze b´ yt reprezenotv´ ana jako ˇretˇezec w nad abecedou V s |w|a = fM (a) pro vˇsechna a ∈ V . Budeme tedy ps´at M = ? w, tj. operator ? je asociov´an s w odpov´ıdaj´ıc´ı multimnoˇziny M . Samozˇrejmˇe vˇsechna slova obdrˇzen´a z w permutac´ı znak˚ u jsou reprezentov´ana stejnou multimnoˇzinou M . ε pˇredstavuje pr´azdnou multimnoˇzinu.
2.1
Definition 1 P kolonie s kapacitou c je struktura Π = (A, e, f, ? vE , B1 , . . . , Bn ), kde • A je abeceda kolonie, jej´ı prvky naz´yv´ ame objekty, • e je z´ akladn´ı objekt kolonie, kter´y naz´yv´ ame enviroment´ aln´ı, e ∈ A, • f je fin´ aln´ı objekt kolonie, f ∈ A, • ? vE je poˇc´ ateˇcn´ı obsah prostˇred´ı, ? vE ∈ (A − {e})◦ , • Bi , 1 ≤ i ≤ n, jsou agenty, kaˇzd´y agent je struktura Bi = (? oi , Pi ), kde – ? oi je multimnoˇzna nad A, kter´ a definuje poˇc´ ateˇcn´ı stav (obsah) agenta Bi a |? oi | = c, – Pi = {pi,1 , . . . , pi,ki } je koneˇcn´ a mnoˇzina program˚ u, kde kaˇzd´y program obsahuje pr´ avˇe c pravidel v jednom z n´ asleduj´ıc´ıch tvar˚ u: a → b, pravidla v dan´em tvaru naz´yv´ ame pˇrepisuj´ıc´ı pravidla, c ↔ d, pravidla v dan´em tvaru naz´yv´ ame komunikaˇcn´ı pravidla, r1 /r2 , pravidla naz´yv´ ame kontroln´ımi pravidly; r1 , r2 jsou pˇrepisuj´ıc´ı nebo komunikaˇcn´ı pravidla.
P kolonie
P kolonie byly zavedeny v pr´ aci [8]. P kolonie je tvoˇrena agenty a prostˇred´ım. Agenty i prostˇred´ı obsahuje objekty. Kaˇzd´ y agent m´ a mnoˇzinu program˚ u. Nejdˇr´ıve uvedeme dva typy pravidel v programech. Prvn´ı typ naz´ yv´ ame pˇrepisuj´ıc´ı pravidla, maj´ı tvar a → b. To znamen´ a, ˇze objekt a uvnitˇr agenta je pˇreps´an (zmˇenˇen) na objekt b. Druh´ y typ pravidel naz´ yv´ame komunikaˇcn´ı pravidla a maj´ı tvar c ↔ d. Pokud je dan´e pravidlo aplikov´ ano, objekt c uvnitˇr agenta a objekt d vnˇe agenta si zamˇen´ı pozice, to znamen´a, ˇze po vykon´ an´ı pravidla objekt d se nach´az´ı uvnitˇr agenta a c je obsaheˇzeno v prostˇred´ı. V pr´aci [7] byla schopnost agent˚ u rozˇs´ıˇrena o kontroln´ı pravidla. T´ımto pravidlem z´ıskali agenty schopnost vybrat si mezi dvˇema moˇznostmi. Pravidla maj´ı tvar r1 /r2 . Pokud je aplikov´ ano kontroln´ı pravidlo, pravidlo r1 m´a vyˇsˇs´ı prioritu pro vykon´ an´ı neˇz pravidlo r2 . To znamen´ a, ˇze agent pokud je to moˇzn´e aplikuje pravidlo r1 , v opaˇcn´em pˇr´ıpade pravidlo r2 . Pokud programy maj´ı jeden typ pravidel, pak hovoˇr´ıme o programech pˇrepisuj´ıc´ıch, komunikaˇcn´ıch nebo kontroln´ıch. V pˇr´ıpadˇe P koloni´ı se dvˇema objekty uvnitˇr kaˇzd´eho agenta pˇrepisuj´ıc´ı programy mo-
Poˇc´ateˇcn´ı konfigurace P kolonie je (n + 1)-tice (? o1 , . . . , ? on , ? vE ) multimnoˇzin objekt˚ u nach´azej´ıc´ıch se v P kolonii na zaˇc´atku v´ ypoˇctu, kde ? oi pro 1 ≤ i ≤ n a pro prostˇred´ı ? vE . Obecnˇe konfigurace P kolonie Π je definovan´a jako (? w1 , . . . , ? wn , ? wE ), kde |? wi | = c, 1 ≤ i ≤ n, ? wi a reprezentuje vˇsechny objekty i-t´eho agenta a ? wE ∈ (A − {e})◦ je souhrn vˇsech objekt˚ u obsaˇzen´ ych v prostˇred´ı a r˚ uzn´ ych od e. V´ ypoˇcet P koloni´ı studovan´ ych v tomto ˇcl´anku prob´ıh´a paralelnˇe. V kaˇzd´em kroku paraleln´ıho v´ ypoˇctu pracuje maxim´aln´ı poˇcet agent˚ u. Kaˇzd´ y agent, kter´ y m˚ uˇze pouˇz´ıt nˇejak´ y ze sv´ ych program˚ u, tak ho pouˇzije. Jestliˇze najde v´ıce neˇz jeden program, pak nedeterministicky vybere pr´avˇe jeden a pouˇzije ho. Pro programy z kaˇzd´e mnoˇziny Pi zavedeme oznaˇcen´ı z mnoˇziny lab (Pi ) takov´e, ˇze lab (Pi ) ∩ lab (Pj ) = ∅ pro i 6= j, 1 ≤ i, j ≤ n. Pro form´aln´ı vyj´adˇren´ı kroku v´ ypoˇctu zavedeme ˇctyˇri funkce: Pro pravidlo r ve tvaru a → b, c ↔ d
73
a c ↔ d/c0 ↔ d0 , resp., pro multimnoˇzinu ? w ∈ A◦ definujeme:
lef t (a → b, ? w) = ? a right (a → b, ? w) = ? b export (a → b, ? w) = ? ε import (a → b, ? w) = ? ε
Konfigurace je koncov´a, pokud mnoˇzina oznaˇcen´ı program˚ u P splˇ nuj´ıc´ı podm´ınky v´ yˇse, nem˚ uˇze b´ yt vybr´ana, jinak neˇz jako pr´azdn´a mnoˇzina. Mnoˇzinu koncov´ ych konfigurac´ı oznaˇc´ıme jako H. Pokud se v´ ypoˇcet zastav´ı, m˚ uˇzeme s n´ım asociovat v´ ysledek v´ ypoˇctu. V´ ysledkem v´ ypoˇctu je poˇcet kopi´ı speci´aln´ıho symbolu f v prostˇred´ı. Mnoˇzina ˇc´ısel poˇc´ıtan´ ych P koloni´ı Π je definov´ana jako
lef t (c ↔ d, ? w) = ? ε right (c ↔ d, ? w) = ? ε export (c ↔ d, ? w) = ? c import (c ↔ d, ? w) = ? d
N (Π) = {
lef t (c ↔ d/c0 ↔ d0 , ? w) = ? ε right (c ↔ d/c0 ↔ d0 , ? w) = ? ε export (c ↔ d/c0 ↔ d0 , ? w) = ? c pro |? w|d ≥ 1 import (c ↔ d/c0 ↔ d0 , ? w) = ? d export (c ↔ d/c0 ↔ d0 , ? w) = ? c0 pro |? w|d = 0 import (c ↔ d/c0 ↔ d0 , ? w) = ? d0 a |? w|d0 ≥ 1
|? wE |f | (? o1 , . . . , ? on , ? vE ) ⇒∗ (? w1 , . . . , ? wn , ? wE ) ∈ H},
– p, p0 ∈ P , p 6= p0 , p ∈ lab (Pj ), p0 ∈ lab (Pi ) , i 6= j,
kde (? o1 , . . . , ? on , ? vE ) je poˇc´ateˇcn´ı konfigurace, (? w1 , . . . , ? wn , ? wE ) je koncov´a konfigurace, a ⇒∗ oznaˇcuje reflexivn´ı a tranzitivn´ı uz´avˇer ⇒. Mˇejme P kolonii Π = (A, e, f, ? vE , B1 , . . . , Bn ). Maxim´aln´ı poˇcet program˚ u asociovan´ ych s agenty naz´ yv´ame v´ yˇskou, poˇcet agent˚ u, n, pak stupnˇem a poˇcet objekt˚ u uvnitˇr kaˇzd´eho agenta kapacitou P kolonie. Oznaˇcme N P COLpar (c, n, h) tˇr´ıdu mnoˇzin ˇc´ısel poˇc´ıt´an´ ych P koloniemi pracuj´ıc´ımi paralelnˇe bez pouˇz´ıt´ı kontroln´ıch pravidel a s: - kapacitou nejv´ yˇse c, - stupnˇem nejv´ yˇse n a - v´ yˇskou nejv´ yˇse h. Pokud pouˇzijeme kontroln´ı pravidla, pak tˇr´ıdu mnoˇzin ˇc´ısel poˇc´ıtan´ ych P koloni´ı oznaˇc´ıme N P COLpar K. Pokud jsou omezeny pouˇzijeme oznaˇcen´ı N P COLpar R respektive N P COLpar KR. Jesltliˇze P kolonie jsou homogenn´ı pouˇzijeme oznaˇcen´ı N P COLpar H respektive N P COLpar KH.
– pro kaˇzd´e p ∈ P , p ∈ lab (Pj ), lef S t (p, ? wE ) ∪ export (p, ? wE ) = ? wj , a import (p, ? wE ) ⊆ ? wE .
2.2
Pro program p a α ∈ {lef t, right, export, import}, necht’ [ α (p, ? w) = α (r, ? w) . r∈p
Zmˇena konfigurace je definov´ ana jako 0 (? w1 , . . . , ? wn , ? wE ) ⇒ (? w10 , . . . , ? wn0 , ? wE ),
kde jsou splnˇeny n´ asleduj´ıc´ı podm´ınky: • Mnoˇzina oznaˇcen´ı program˚ u P s |P | ≤ n takov´a, ˇze
Registrov´ y stroj
p∈P
V naˇsem pˇr´ıspˇevku porovn´av´ame tˇr´ıdy N P COLpar (c, n, h) s rekuzivnˇe spoˇcetn´ ymi mnoˇzinami ˇc´ısel. Pro d˚ ukaz v´ ypoˇcetn´ı s´ıly pouˇzijeme registrov´ y stroj.
• Kromˇe toho, vybran´ a mnoˇzina P je maxim´aln´ı, to znamen´ a , ˇ z e ˇ z a ´ dn´ y dalˇs´ı program r ∈ S lab (P ), r ∈ / P , nem˚ uˇze b´ yt pˇrid´an do i 1≤i≤n mnoˇziny P tak, aby splˇ noval podm´ınky dˇr´ıve uveden´e
Definition 2 [9] Registrov´y stroj je struktura M = (m, H, l0 , lh , P ) kde: - m je poˇcet registr˚ u, - H je mnoˇzina oznaˇcen´ı instrukc´ı, - l0 je oznaˇcen´ı pro poˇc´ ateˇcn´ı / startovn´ı instrukci, - lh je oznaˇcen´ı pro koncovou instrukci, - P je koneˇcn´ a mnoˇzina instrukc´ı maj´ıc´ı sv´e oznaˇcen´ı urˇcen´e pomoc´ı mnoˇziny H.
Obecnˇe pro kaˇzd´e j, 1 ≤ j ≤ n, pro kter´e existuje a p ∈ P s p ∈ lab (Pj ), necht’ wj0 = right (p, ? wE ) ∪ import (p, ? wE ) . Pokud neexistuje p ∈ P s p ∈ lab (Pj ) pro nˇejak´e j, 1 ≤ j ≤ n, necht’ ? wj0 = ? wj a d´ale necht’ [ [ 0 import (p, ? wE )∪ export (p, ? wE ) . ? wE = ? wE − p∈P
p∈P
Sjednocen´ı a ”-” zde pˇredstavuj´ı operace nad multimnoˇzinami.
Instrukce registrov´eho stroje maj´ı n´asleduj´ıc´ı tvary:
74
l1 :
(ADD(r), l2 , l3 ) K obsahu registru r pˇriˇcte 1 a v´ ypoˇcet pokraˇcuje instrukc´ı (oznaˇcenou) l2 nebo l3 .
• agenty Bi = (? e, Pi ), 1 ≤ i ≤ |H| + 3, a jejich programy jsou n´asleduj´ıc´ı:
l1 :
(SU B(r), l2 , l3 ) Pokud registr r nen´ı pr´ azdn´ y, tak odeˇcte z jeho obsahu 1 a pokraˇcuje instrukc´ı l2 , jinak (registr r obsahuje 0) pokraˇcuje instrukc´ı l3 .
1. Mˇejme strartovac´ı agenty B1 , B2 s mnoˇzinami program˚ u: P1 : 1 : he → l0 i 2 : hl0 ↔ D/l0 ↔ ei
lh :
HALT Stroj zastav´ı. Pro tuto instrukci je pˇriˇrazeno pouze jedin´e koncov´e oznaˇcen´ı lh . Bez ztr´aty na obecnosti m˚ uˇzeme pˇredpokl´adat, ˇze v kaˇzd´e ADD-instrukci l1 : (ADD(r), l2 , l3 ) a v kaˇzd´e SU B-instrukci l1 : (SU B(r), l2 , l3 ) je oznaˇcen´ı l1 , l2 , l3 navz´ajem r˚ uzn´e. Registrov´ y stroj M poˇc´ıt´ a mnoˇzinu N (M ) ˇc´ısel n´asleduj´ıc´ım zp˚ usobem: na zaˇc´ atku jsou vˇsechny registry pr´azdn´e (je v nich uloˇzeno ˇc´ıslo nula) s instrukc´ı oznaˇcenou l0 a pˇrejdeme k aplikov´an´ı instrukc´ı urˇcen´ ych pomoc´ı oznaˇcen´ı (doc´ıl´ıme pomoc´ı obsahu registr˚ u). Pokud dojdeme ke koncov´e instrukci, pak ˇc´ıslo uloˇzen´e v dan´em okamˇziku v registru 1 pˇredstavuje v´ ysledek z´ıskan´ y registrov´ ym strojem M a od t´eto chv´ıle pˇredstavuje N (M ). (Kv˚ uli nedeterminismu ve vyb´ır´ an´ı pokraˇcov´ an´ı v´ ypoˇctu v pˇr´ıpadˇe ADD-instrukc´ı N (M ) m˚ uˇze b´ yt nekoneˇcn´a.) T´ımto zp˚ usobem v´ ypoˇctu m˚ uˇzeme vypoˇc´ıta vˇsechny mnoˇziny ˇc´ısel, kter´e jsou vypoˇcitateln´e Turingov´ ym strojem. [9]
3
P2 : 1 : he → Di 2 : hD ↔ l0 i
Agent B1 generuje a pos´ıl´a kopie oznaˇcen´ı pro startovac´ı instrukci l0 registrov´eho stroje M a zastav´ı se pˇr´ıjmut´ım jedn´e kopie objektu D. Druh´ y agent B2 generuje jednu kopii objektu D a dalˇs´ı v´ ypoˇcet agenta je zastaven pomoc´ı symbolu l0 . Simulace v´ ypoˇctu m˚ uˇze zaˇc´ıt druhou kopi´ı objektu l0 v prostˇred´ı. 2. Potˇrebujeme jednoho speci´aln´ı objekt d.
agenta
generuj´ıc´ıho
P3 : 1 : he → di 2 : hd ↔ H/d ↔ ei V kaˇzd´em druh´em kroku agent B3 um´ıst´ı jeden objekt d do prostˇred´ı. 3. Pro kaˇzdou instrukci l1 : (ADD(r), l2 , l3 ) je zde agent P kolonie Π. Dan´ y agent pˇrid´av´a jeden objekt ar a objekt l2 nebo l3 do prostˇred´ı.
P kolonie s jedn´ım objektem uvnitˇ r agenta
Pl1 1: 2: 3:
V t´eto ˇc´asti se budeme zab´ yvat vlastnostmi P kolonie pouze s jedn´ım objektem uvnitˇr kaˇzd´eho agenta P kolonie. To znamen´ a, ˇze kaˇzd´ y program agenta je tvoˇren pouze jedn´ım pravidlem a to pˇrepˇrepisuj´ıc´ım, komunikaˇcn´ım nebo kontroln´ım.
: he ↔ l1 i hl1 → ar i har ↔ di
4 : hd → l2 i 5 : hd → l3 i 6 : hl2 ↔ e/l3 ↔ ei
Jakmile je objekt l1 pˇr´ıtomn´ y v prostˇred´ı, agent Bl1 m˚ uˇze zaˇc´ıt pracovat, odeb´ır´a z prostˇred´ı objekt l1 a generuje m´ısto nˇej objekt ar , nakonec vymˇen´ı objekt l2 nebo l3 za e. Na z´avˇer t´eto ˇc´asti v´ ypoˇctu je objekt s oznaˇcen´ım dalˇs´ı instrukce stroje M um´ıstˇen do prostˇred´ı a dalˇs´ı agent zaˇc´ın´a pracovat.
Theorem 1 N P COLpar K(1, ∗, 6) = N RE.
D˚ ukaz: Uvaˇzujme registrov´ y stroj M = (m, H, l0 , lh , P ). Vˇsechna oznaˇcen´ı z mnoˇziny H budou objekty z P kolonie. Obsah registru i bude reprezentov´an poˇctem kopi´ı objekt˚ u ai v prostˇred´ı. Zkonstruujeme P kolonii Π = (A, f, e, B1 , . . . , Bn ) s:
4. Pro kaˇzdou instrukci l1 : (SU B(r), l2 , l3 ) z mnoˇziny P uvaˇzujme agenta Bl1 s mnoˇzinou program˚ u: Pl1 1: 2: 3:
• abecedou A = H ∪ {ai | 1 ≤ i ≤ m} ∪ {Fi | 1 ≤ i ≤ |H|} ∪ {e, d, D} • koncov´ ym objektem f = a1
75
: he ↔ l1 i 4: har → l2 /d → l3 i hl1 → F1 i 5: hl2 ↔ e/l3 ↔ ei hF1 ↔ ar / F1 ↔ di
• f = a1 ,
Agent znovu pˇriv´ ad´ı dovnitˇr objekt l1 a mˇen´ı ho za objekt F1 . V dalˇs´ım kroku agent zkontroluje zda-li je v prostˇred´ı nejm´enˇe jeden objekt ar . Jestliˇze ano, agent vezme dovnitˇr ar a pˇrep´ıˇse ho na objekt l2 . Pokud se objekt ar v prostˇred´ı nevyskytuje, agent vezme objekt d a pˇrep´ıˇse ho na objekt l3 . V posledn´ım kroku agent vˇzdy znovu zamˇen´ı objekt l2 nebo l3 za e.
• B = (? ee, P ) Na zaˇc´atku v´ ypoˇctu agent generuje objekt l0 (oznaˇcen´ı startovac´ı instrukce registrov´eho stroje M ) a dvˇe kopie objekt˚ u a. Agent zaˇc´ın´a simulaci instrukce oznaˇcen´e l0 a generuje oznaˇcen´ı n´asleduj´ıc´ı instrukce. Mnoˇzina program˚ u obsahuje:
5. Pro koncovou instrukci oznaˇcenou lh budeme m´ıt agenta Blh s programy: Plh : 1 : he ↔ lh i 2 : hlh → Hi
1. Pro innicializaci simulace: P : 1: 2: 3: 4: 5: 6:
3 : hH ↔ di
Agent zpotˇrebov´ av´ a objekt lh a v prostˇred´ı nen´ı dalˇs´ı objekt lm . Tento agent um´ıst´ı jednu kopii objektu H do prostˇred´ı a zastav´ı svou ˇcinnost. Objekt H je v dalˇs´ım kroku zpotˇrebov´ an agentem B3 . Neexistuje agent, kter´ y by mohl zaˇc´ıt pracovat a v´ ypoˇcet konˇc´ı.
7: 8: 9: 10 : 11 : 12 : 13.
hse → f gi hf g ↔ aei hae → al0 i hal0 ↔ gei hge ↔ hl0 i hhl0 ↔ aai hsa → sai
Agent s dvˇema kopiemi objektu a uvnitˇr je pˇripraven pro simulov´an´ı instrukce oznaˇcen´e li (s objektem li um´ıstˇen´em v prostˇred´ı). Toho je dosaˇzeno n n´asleduj´ıc´ımi kroky: Agent zaˇc´ın´a v´ ypoˇcet generov´an´ım objektu d. Pro dalˇs´ı kroky v´ ypoˇctu mus´ı generovat ˇctyˇri objekty d. Druh´a dvojice objekt˚ u d m˚ uˇze b´ yt pˇreps´ana na pomocn´e objekty s a a. Program 13 zajiˇst’uje zacyklen´ı v´ ypoˇctu, pokud poˇcet kop´ı objketu d nen´ı dostateˇcn´ y. V dalˇs´ıch kroc´ıch agent generuje druh´ y objekt a, objekt h a dalˇs´ı pomocn´e symboly (z d˚ uvodu dodrˇzen´ı posloupnosti krok˚ u v´ ypoˇctu) a koneˇcnˇe oznaˇcen´ı l0 . Pokud jsou uvnitˇr agenta dvˇe kopie objektu a, agent je pˇripraven pro simulaci instrukce oznaˇcen´e li (Pokud objekt li je um´ıstˇen v prostˇred´ı). Inicializace je vykon´ana pomoc´ı n´asleduj´ıc´ı posloupnost´ı krok˚ u:
Uk´azali jsme, ˇze P kolonie Π simuluje v´ ypoˇcet registrov´eho stroje M . V´ ypoˇcet P kolonie Π zaˇc´ın´a bez objekt˚ u ar v prostˇred´ı, stejn´ ym zp˚ usobem zaˇc´ın´a v´ ypoˇcet registrov´eho stroje M s nulami ve vˇsech registrech. V´ ypoˇcet Π konˇc´ı pokud symbol lh je um´ıstˇen dovnitˇr odpov´ıdaj´ıc´ıho agenta, stejn´ ym zp˚ usobem registrov´ y stroj M konˇc´ı ˇcinnost po vykon´ an´ı koncov´e instrukce oznaˇcen´e lh . Plat´ı tedy N (M ) = N (Π), a protoˇze kaˇzd´ y agent m´ a nejv´ yˇse 6 program˚ u, d˚ ukaz je kompletn´ı. Dalˇs´ı ot´azkou je, jak´ y poˇcet agent˚ u je nutn´ y pro simulov´an´ı registrov´eho stroje. V pr´ aci [2] je dok´az´ano: Theorem 2 N P COLpar K(1, 4, ∗) = N RE
4
hee → ddi hdd ↔ eei hdd → sai hsa ↔ edi hed → hai hha ↔ sei
P kolonie se dvˇ ema objekty uvnitˇ r agent˚ u
konfigurace Π
Agenty se dvˇema objekty maj´ı v kaˇzd´em programu dvˇe pravidla. Pokud pravidla v programech jsou stejn´eho typu, P kolonii naz´ yv´ ame homogenn´ı.
krok 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.
Theorem 3 N P COLpar HK(2, 1, ∗) = N RE.
D˚ ukaz: Mˇejme registrov´ y stroj M s m registry. Zkonstruujeme P kolonii Π = (A, f, e, B) simuluj´ıc´ı v´ ypoˇcet registrov´eho stroje M s: • A = {d, a, s, f, h, v} ∪ {l, l0 | l ∈ H} ∪ {ar | 1 ≤ r ≤ m},
76
B
Env
? ee ? dd ? ee
? dd
? dd
? dd
? sa
? dd
? ed
? sad
? ha
? sad
? se
? haad
?f g
? haad
? ae
? f ghad
oznaˇ cen´ı aplikovateln´ ych program˚ u
P 1 2 nebo 3 1 2 nebo 3 4 nebo 13 5 6 7 8 9
konfigurace Π
krok 11. 12. 13. 14.
B ? al0 ? ge ? hl0 ? aa
pr´azdn´ y). V pˇr´ıpadˇe, ˇze ano, pˇr´ıd´a l1 s ar dovnitˇr, v pˇr´ıpadˇe, ˇze ne, l1 vstoup´ı do agenta se symbolem e. V z´avislosti na obsahu agenta generuje objekt l2 nebo l3 .
oznaˇ cen´ı aplikovateln´ ych program˚ u
Env ? f ghad ? l0 f haad ? gf aad ? l0 gf d
P 10 11 12 ?
V pˇr´ıpadˇe kdy registr r je pr´azdn´ y: konfigurace Π
krok 1. 2. 3. 4.
Pokud agent pouˇzije program 3 ve druh´em kroku mus´ı v dalˇs´ıch kroc´ıch pouˇz´ıt program 13 a v´ ypoˇcet nikdy neskonˇc´ı. Pokud je v´ıce neˇz jeden aplikovateln´ y program, agent vybere napsan´ y tuˇcnˇe a vykon´ a jej.
B
Env
? aa
? l1 f ghd
? l1 e
? f ghdaa
? l3 v
? f ghdaa
? aa
? l3 vf ghd
konfigurace Π
haa ↔ l1 ei hel1 → l20 ar i hel1 → l30 ar i hl20 ar ↔ ef i hl30 ar ↔ ef i hef ↔ el20 i
20 : 21 : 22 : 23 : 24 :
hef ↔ el30 i hel20 → l2 vi hel30 → l3 vi hl2 v ↔ aai hl3 v ↔ aai
krok 1. 2. 3. 4.
krok 1. 2. 3. 4. 5. 6. 7.
B
Env
? aa
? l1 f ghd
? l1 e 0 ? l2 ar
? f ghdaa
? ef 0 ? l2 e
? f ghdaa 0 ? l2 ghdaaar ? f ghdaaar
? l2 v
? f ghdaaar
? aa
? l2 vf ghdaaar
B ? aa ? l1 ar ? l2 v ? aa
Env n ? l1 f ghdar n−1 ? f ghdaaar n−1 ? f ghdaaar n−1 ? l2 vf ghdar
oznaˇ cen´ı aplikovateln´ ych program˚ u
P 25 26 28 ?
4. Pro koncovou instrukci lh je v mnoˇzinˇe program˚ u program:
Kdyˇz agent vezme objekty l1 a e dovnitˇr, pˇrep´ıˇse je na ar a l20 nebo l30 . Dalˇs´ı kroky konˇc´ı generov´an´ım l2 nebo l3 . Tento objekt mus´ı b´ yt posl´an ven do prostˇred´ı s objektem v. konfigurace Π
P 25 27 29 ?
V´ ypoˇcet v pˇr´ıpade, kdy registr r nen´ı pr´azdn´ y:
2. Pro kaˇzdou ADD-instrukci l1 : (ADD(r), l2 , l3 ) pˇrid´ame do mnoˇziny program˚ u P: P : 14 : 15 : 16 : 17 : 18 : 19 :
oznaˇ cen´ı aplikovateln´ ych program˚ u
P : haa ↔ hlh i
oznaˇ cen´ı aplikovateln´ ych program˚ u
Po probˇehnut´ı tohoto programu P kolonie ukonˇc´ı v´ ypoˇcet, stjnˇe jako registrov´ y stroj zastav´ı sv˚ uj v´ ypoˇcet.
P 14 15 nebo 16 17 19 21 23 ?
Uk´azali jsme, ˇze P kolonie Π simuluje ˇcinnost registrov´eho stroje M a ˇc´ıslo z´ıskan´e v prvn´ım registru registrov´eho stroje M odpov´ıd´a poˇctu kopi´ı objekt˚ u a1 v prostˇred´ı P kolonie Π. Theorem 4 N P COLpar HK(2, ∗, 4) = N RE. D˚ ukaz: Mˇejme registrov´ y stroj M = (m, H, l0 , lh , P ). Vˇsechna Oznaˇcen´ı z mnoˇziny H budou objekty P kolonie, prvky mnoˇziny uvedeme d´ale. Obsah registru i bude reprezentov´an poˇctem kopi´ı urˇcit´ ych objket˚ u ai prostˇred´ı. Zkonstruujeme P kolonii Π = (A, f, e, B1 , . . . , Bn ) s:
3. Pro kaˇzdou SU B-instrukci l1 : (SU B(r), l2 , l3 ) je podmnoˇzina program˚ u: P : 25 : ha ↔ l1 / a ↔ l1 ; a ↔ ar / a ↔ ei 26 : hl1 ar → l2 vi 28 : hl2 v ↔ aai 27 : hl1 e → l3 vi 29 : hl3 v ↔ aai
• abecedou A = H ∪ {ai | 1 ≤ i ≤ m} ∪ {Fi | 1 ≤ i ≤ |H|} ∪ {e, d, D}
V prvn´ım korku agent kontroluje, zda-li se ar nevyskytuje v prostˇred´ı (pokud registr r nen´ı
• koncov´ ym objektem f = a1
77
• agent Bi = (? ee, Pi ), 1 ≤ i ≤ |H| + 2, a jeho programy:
konfigurace Π
krok 1. 2. 3. 4.
1. Uvaˇzujme startovac´ı agenty B1 , B2 s mnoˇzinou program˚ u: P1 : 1 : hee → el0 i 2 : he ↔ e/e ↔ e; l0 ↔ D/l0 ↔ ei
Pl1 1: 2: 3:
Agent B1 generuje dvˇe poˇc´ ateˇcn´ı oznaˇcen´ı registrov´eho stroje M a zastav´ı se pˇrijet´ım jedn´e kopie objektu D. Druh´ y agent B2 generuje jednu kopii objektu D a ˇcek´ a na objekt l0 . Pokud je objekt pˇresunu dovnitˇr agenta, ukonˇc´ı agent svou ˇcinnost. Simulace v´ ypoˇctu m˚ uˇze zaˇc´ıt s druhou kopi´ı objektu l0 v prostˇred´ı. Zaˇc´atek v´ ypoˇctu m˚ uˇze prob´ıhat n´ asledovnˇe:
krok 1. 2. 3. 4. 5.
B1 ? ee ? el0 ? ee ? el0 ? De
B2 ? ee ? De ? De ? el0 ? el0
Env
? el0 ? De ? el0
? l1
? ar l2
: he ↔ l1 /e ↔ l1 ; e ↔ ar /e ↔ ei har → l2 /e → l3 ; l1 → v/l1 → vi hl2 ↔ e/l3 ↔ e; v ↔ e/v ↔ ei
V´ ypoˇcet pro pˇr´ıpad, kdy registr r nen´ı pr´azdn´ y: konfigurace Π
P2 1 −−− 2 −−− −−−
krok 1. 2. 3. 4.
2. Pro kaˇzdou instrukci l1 : (ADD(r), l2 , l3 ) je v P kolonii Π jeden agent. Dan´ y agent mus´ı pˇridat do prostˇred´ı jednu kopii objektu ar a objekt l2 nebo l3 . Pl1 1: 2: 4:
Pl1 1 2 nebo 3 4 ?
Agent vˇzdy pˇriv´ad´ı dovnitˇr objekt l1 a jednu kopii ar (pokud je nˇejak´a kopie ar v prostˇred´ı). Jestliˇze ano, agent generuje objekt l2 . Jestliˇze ne, agent generuje objekt l3 . V dalˇs´ım kroku agent vˇzdy zamˇen´ı objekt l2 nebo l3 za e.
oznaˇ cen´ı aplikovateln´ ych program˚ u
P1 1 2 1 2 −−−
Env
3. Pro kaˇzdou instrukci l1 : (SU B(r), l2 , l3 ) z mnoˇziny P pouˇzijeme agenta Bl1 s n´asleduj´ıc´ı mnoˇzinou program˚ u:
P2 : 1 : hee → Dei 2 : hDe ↔ el0 i
konfigurace Π
B l1 ? ee ? el1 ? ar l2 ? ee
oznaˇ cen´ı aplikovateln´ ych program˚ u
B l1 ? ee ? ar l1 ? l2 v ? ee
Env ? l1 ar
? l2 v
oznaˇ cen´ı aplikovateln´ ych program˚ u
Pl1 1 2 3 ?
V´ ypoˇcet pro pˇr´ıpad, kdy registr r je pr´azdn´ y: konfigurace Π
krok 1. 2. 3. 4.
: hee ↔ el1 i 3 : hel1 → ar l3 i hel1 → ar l2 i har ↔ e/ar ↔ e; l2 ↔ e/l3 ↔ ei
Pokud objekt l1 je obsaˇzen v prostˇred´ı, agent Bl1 m˚ uˇze zaˇc´ıt pracovat, odeb´ırat objekt l1 , generovat ar a l2 nebo l3 . Na z´ avˇer t´eto ˇc´asti v´ ypoˇctu objekt s oznaˇcen´ım dalˇs´ı instrukce registrov´eho stroje M je um´ıstˇen do prostˇred´ı a dalˇs´ı agent m˚ uˇze zaˇc´ıt pracovat.
B l1 ? ee
Env ? l1
? el1 ? el3 ? ee
? l3 v
oznaˇ cen´ı aplikovateln´ ych program˚ u
Pl1 1 2 3 ?
4. Pro koncovou instrukci lh nen´ı zde program ani ˇz´adn´ y agent P kolonie. 5. Druh´a moˇzn´a posloupnosti krok˚ u na ˇzaˇc´atku je tato:
78
konfigurace Π
krok 1. 2. 3. 4. 5. 6.
B1 B2 B l0 ? ee ? ee ? ee ? el0 ? De ? ee ? ee ? De ? ee ? el0 ? De ? el0 ? ee ? De ??? ??? ? De ? el0
Membrane Computing. Proc. Intern. Workshop, WMC 2007, Thessaloniki, Greece, June 2007 (G. Eleftherakis et al., eds.), LNCS 4860, Springer, Berlin, 2007, pp. 193–208.
oznaˇ cen´ı aplikovateln´ ych program˚ u
Env
? el0 ? el0
P1 1 2 1 2 1 −
P2 1 − − − 2 −
Pl0 − − 1 2
[3] Csuhaj-Varj´ u, E. — Kelemen, J. — Kelemenov´a, A. — P˘aun, Gh. — Vaszil, G.: Cells in environment: P colonies, Journal of Multiple-valued Logic and Soft Computing 12, 3-4, 2006, pp. 201– 215. [4] Csuhaj-Varj´ u, E. — Margenstern, M. — Vaszil, G.: P colonies with a bounded number of cells and programs. Pre-Proceedings of the 7th Workshop on Membrane Computing (H. J. Hoogeboom, Gh. P˘aun, G. Rozenberg, eds.), Leiden, The Netherlands, 2006, pp. 311–322.
Uk´azali jsme, ˇze P kolonie Π simuluje ˇcinnost registrov´eho stroje M . V´ ypoˇcet Π zaˇc´ın´ a s ˇz´ adn´ ym objektem ar um´ıstˇen´ ym v prostˇred´ı, stejnˇe jako registrov´ y stroj M zaˇc´ın´ a s nulou na vˇsech registrech. V´ ypoˇcet Π se zastav´ı pokud symbol lh je um´ıstˇen dovnitˇr odpov´ıdaj´ıc´ıho agenta, stejnˇe jako registrov´ y stroj M se zastav´ı vykon´ an´ım koncov´e instrukce oznaˇcen´e lh . Plat´ı tedy, N (M ) = N (Π), a protoˇze kaˇzd´ y agent obsahuje nejv´ yˇse pˇet program˚ u, d˚ ukaz je hotov.
5
[5] Freund, R. — Oswald, M.: P colonies working in the maximally parallel and in the sequential mode. Pre-Proceedings of the 1st International Workshop on Theory and Application of P Systems (G. Ciobanu, Gh. P˘aun, eds.), Timisoara, Romania, 2005, pp. 49–56.
Z´ avˇ er
[6] Kelemen, J. — Kelemenov´a, A.: A grammartheoretic treatment of multi-agent systems. Cybernetics and Systems 23, 1992, pp. 621–633.
Homogenn´ı P kolonie jsou v´ ypoˇcetnˇe u ´pln´e pro: 1. c = 1, h = 6 a neomezen´e n (P kolonie s jedn´ım objektem uvnitˇr kaˇzd´eho agenta, s pouˇzit´ım nejv´ yˇse ˇsest program˚ u)
[7] Kelemen, J. — Kelemenov´a, A.: On P colonies, a biochemically inspired model of computation. Proc. of the 6th International Symposium of Hungarian Researchers on Computational Intelligence, Budapest TECH, Hungary, 2005, pp. 40–56.
2. c = 1, n = 4 a neomezen´e h (P kolonie sestaven´ a ze ˇctyˇr agent˚ u, kaˇzd´ y z n´ıch m´a uvnitˇr pouze jeden objekt) 3. c = 2, h = 4 a neomezen´e n (P kolonie se dvˇema objekty uvnitˇr kaˇzd´eho agenta, s pouˇzit´ım nejv´ yˇse ˇctyˇr program˚ u)
[8] Kelemen, J. — Kelemenov´a, A. — P˘aun, Gh.: Preview of P colonies: A biochemically inspired computing model. Workshop and Tutorial Proceedings, Ninth International Conference on the Simulation and Synthesis of Living Systems, ALIFE IX (M. Bedau at al., eds.) Boston, Mass., 2004, pp. 82–86.
4. c = 2, n = 1 a neomezen´eh (P kolonie s jedn´ım agentem, kter´ y zpracov´av´a dva symboly). Pro dan´e v´ ysledky byla pouˇzita simulace registrov´eho stroje. V´ yzkum simulace operace ADD urˇcuje obdrˇzen´e v´ ysledky.
[9] Minsky, M. L.: Computation: Finite and Infinite Machines. Prentice Hall, Engle-wood Cliffs, NJ, 1967. [10] P˘aun, Gh.: Computing with membranes. Journal of Computer and System Sciences 61, 2000, pp. 108–143.
Literatura [1] Ciencialov´a, L. — Cienciala, L.: Variations on the theme: P colonies, Proceedings of the 1st International workshop WFM’06 (Kol´ aˇr, D., Meduna, A., eds.), Ostrava, 2006, pp. 27–34.
[11] P˘aun, Gh.: Membrane computing: An introduction. Springer-Verlag, Berlin, 2002. [12] P systems web page. 15. leden 2001. 27. u ´nora 2008
[2] Cienciala, L. — Ciencialov´ a, L. — Kelemenov´a, A.: On the Number of Agents in P colonies,
79
80