Homogenní P kolonie 1

Homogenn´ı P kolonie1 Ludˇ ek Cienciala1 , Lucie Ciencialov´ a1 , Alica Kelemenov´ a1,2 1´

Ustav informatiky, Slezská univerzita Opava Bezruˇcovo nám.13, 746 01 Opava

2

Katedra informatiky, Katolická univerzita Ruˇzomberok, N´ amestie A. Hlinku 56/1, 034 01 Ruˇzomberok, Slovenská republika [email protected], [email protected], [email protected]

Abstrakt

pˇredáván´ı informac´ı mezi agenty, kdy jeden agent vylouˇc´ı do prostˇred´ı urˇcitou látku odpov´ıdaj´ıc´ı jeho stavu v dané 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án´ı pach˚ u patˇr´ı to, ˇze mravenc˚ um staˇc´ı i mal´ y mozeˇcek k vytvoˇren´ı pomˇernˇe sloˇzité spoleˇcenské struktury. Existuj´ı vˇsak parazité, kteˇr´ı jsou schopni napodobit mravenˇc´ı pach a z toho vypl´ yvá snadná napadnutelnost daného systému. Mezi ˇcast´ ymi parazity mravenc˚ u jsou mravenci jiného druhu. Nyn´ı se pod´ıvejme ˇ na druh´ y pˇr´ıklad a to vˇcely. Zihadlov´ y aparát vˇcely tvoˇr´ı nˇekolik ˇzláz. V jejich v´ ymˇeˇsc´ıch je histamin, fosfolipáza a hyaluronidáza vyvolávaj´ıc´ı nepˇr´ıjemné pocity svˇedˇen´ı a pálen´ı v okol´ı vpichu. Tyto ˇzlázy také vyluˇcuj´ı i feromony, které slouˇz´ı k vyvolán´ı poplachu u ostatn´ıch vˇcel. Do rány vstˇrikuj´ı vˇcely i látku pˇripom´ınaj´ıc´ı v˚ uni banán˚ u. Pomoc´ı n´ı se orientuj´ı dalˇs´ı vˇcely a vpichuj´ı dalˇs´ı ˇzihadla do bl´ızkosti prvn´ıho, tzn. u kaˇzdé dávky jedu je i dávka izoamylacetátu. Izoamylacetát je stálá látka informuj´ıc´ı nˇeco okolo 10 minut dalˇs´ı vˇcely, kde se nacház´ı ”nepˇr´ıtel”. Vˇcely z jednoho u ´lu se poznáj´ı podle specifické v˚ unˇe, podobné u ´lové v˚ uni, která sestává 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á stejnˇe, z d˚ uvodu, ˇze b´ yvá sb´ırán jednak z r˚ uzn´ ych rostlin, ale hlavnˇe v r˚ uzném pomˇeru tˇechto rostlin. Povrch tˇela vˇcely je uzp˚ usoben tak, ˇze nab´ırá 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á v˚ uni kvˇet˚ u meduˇ nky nebo plod˚ u kdoule. Pomáhaj´ı vˇcelám naj´ıt i cestu zpátky do u ´lu. Pro orientaci slouˇz´ı vˇcelám i tance uvnitˇr u ´lu a mnoho dalˇs´ıch v˚ un´ı. Napˇr. terpeny, aldehydy, ketony i dalˇs´ı ˇstiplavé a aromatické slouˇceniny v r˚ uzn´ ych mnoˇzstv´ıch ovlivˇ nuj´ı dorozum´ıván´ı vˇcel a umoˇzn ˇuj´ı fungován´ı vˇcelstva. V˚ uni vˇcely pouˇz´ıvaj´ı

V pˇr´ıspˇevku prezentujeme v´ ysledky z´ıskané pˇri v´ yzkumu P koloni´ı, jedné z variant v´ ypoˇcetn´ıch model˚ u zaloˇzen´ ych na nez´ avisl´ ych membr´ anov´ ych agentech, které se vyv´ıj´ı a p˚ usob´ı ve spoleˇcném prostˇred´ı. Budeme se zab´ yvat pˇredevˇs´ım P koloniemi, které 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ém 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ého agenta.

1

´ Uvod

P kolonie byly zavedeny v pr´ aci [8] jako jeden z model˚ u inspirovan´ ych membr´ anov´ ymi systémy ([10]) a gramatick´ ymi systémy, které naz´ yv´ ame kolonie ([6]). Dan´ y model je inspirov´ an strukturou a ˇcinnost´ı ˇziv´ ych organism˚ u ve spoleˇcném prostˇred´ı. Autonomn´ı organismy ˇzij´ıc´ı v P kolonii naz´ yváme 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ém modelu. Agenty i jejich ˇzivotn´ı projevy jsou definovány 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ého agenta urˇcuje tzv. kapacita P kolonie. Objekty P koloni´ı si m˚ uˇzeme pˇredstavit v pˇr´ırodˇe jako látky, které jsou schopny dané organismy mˇenit, pˇrij´ımat, vyluˇcovat do prostˇred´ı. I takto jednoduché ˇzivotn´ı projevy mohou emergovat v mnohem sloˇzitˇejˇs´ı ˇzivotn´ı projevy celé P kolonie. Nejv´ıce k tomu pˇrisp´ıvá

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ázej´ı speciáln´ı objekty, které naz´ yv´ ame enviromentáln´ı 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á 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ém 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án´ı ostatn´ıch agent˚ u v dalˇs´ım kroku v´ ypoˇctu. V pˇr´ırodˇe se také ˇcasto prostˇred´ı vyuˇz´ıvá jako komunikaˇcn´ı kanál. Nˇekteré organismy vyluˇcuj´ı jisté látky do prostˇred´ı a t´ım ovlivˇ nuj´ı chován´ı ostatn´ıch. V´ ypoˇcet je paraleln´ı. V kaˇzdém kroku v´ ypoˇctu kaˇzd´ y agent nedeterministicky vybere jeden ze sv´ ych aplikovateln´ ych program˚ u a vykoná jej. V´ ypoˇcet konˇc´ı zastaven´ım, kdy ˇzádn´ y agent nem˚ uˇze aplikovat ˇzádn´ 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é. Zajimavá je otázka, jak´ y je nejmenˇs´ı poˇcet agent˚ u, poˇcet program˚ u v agentu pˇri zachován´ı v´ ypoˇcetn´ı u ´plnosti. V tomto pˇr´ıspˇevku popisujeme vlastnosti homogenn´ıch P koloni´ı , to znamená 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á P kolonie s kapacitou jedna je homogenn´ı. Homogenn´ı P kolonie byly poprvé studovány v [1]. Budeme se zab´ yvat poˇctem agent˚ u a poˇctem program˚ u v agentech pˇri zachován´ı v´ ypoˇcetn´ı u ´plnosti homogenn´ıch P koloni´ı s kapacitou jedna a dvˇe. To znamená, ˇze vˇsechny agenty bude v prvn´ım pˇr´ıpadˇe obsahovat jeden objekt a ve druhém pˇr´ıpadˇe dva objekty. V následuj´ıc´ı kapitole uvedeme základn´ı definice, definici P kolonie a definici registrového 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ého agenta. V [1] jsme ukázali, ˇze v nejlepˇs´ım pˇr´ıpadˇe sedm program˚ u u kaˇzdého agenta, stejnˇe tak i pˇet agent˚ u zabezpeˇcuje v´ ypoˇcetn´ı u ´plnost P koloni´ı. V ˇclánku ukáˇzeme, ˇze ˇsest program˚ u v kaˇzdém 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ém agentu uvedeme v kapitole 4. Dva objekty v agentech dovoluj´ı maximálnˇe sn´ıˇzit poˇcet agent˚ u tak, ˇze v´ ypoˇcetn´ı u ´plnost m˚ uˇze b´ yt realizována pouze jedn´ım agentem. Nav´ıc ˇctyˇri programy v kaˇzdém 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án, 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é pravidlo z dané 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ávˇe ta pravidla, pomoc´ı kter´ ych urˇcité organismy komunikuj´ı. Jedn´ a l´ atka c je vylouˇcena do prostˇred´ı a dalˇs´ı l´ atka d, je pˇrijata organismem. Látku 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é chován´ı tomuto nedostatku. To znamen´ a napˇr´ıklad mravenec pokud nenajde, ztrat´ı feromonovou stopu, bude ji dále hledat a pokud ji najde, bude ji sledovat.

2

V´ ypoˇcet zaˇc´ın´ a v poˇc´ ateˇcn´ı konfiguraci, která je definována n´ asleduj´ıc´ım zp˚ usobem: prostˇred´ı a vˇsechny agenty obsahuj´ı pouze kopie objekt˚ u e. Aplikován´ım program˚ u agenty mohou mˇenit sv˚ uj ob-

Definice

Budeme pˇredpokládat, ˇze ˇctenáˇri jsou známy základn´ı definice a poznatky z teorie formáln´ıch jazyk˚ u a automat˚ u. V´ıce informac´ı o membránov´ 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ány na tvar hab → cdi. Stejn´ ym zp˚ usobem m˚ uˇzeme modifikovat komunikaˇcn´ı programy na tvar hab ↔ cdi.

ˇcásteˇcnˇe v [9] a [6, 7, 8]. Poˇcet ˇcl´ ank˚ u o daném modelu neustále roste, nejlépe se o tom m˚ uˇzeme pˇresvˇedˇcit na webov´ ych stránk´ ach [12]. Uvedeme zde oznaˇcen´ı pouˇzité 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áporn´ ych cel´ ych ˇc´ısel. Σ je oznaˇcen´ı pro abecedu. Necht’ Σ∗ je mnoˇzina vˇsech slov nad abecedou Σ (vˇcetnˇe pr´ azdného slova ε). Pro délku 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ému 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át M = ? w, tj. operator ? je asociován s w odpov´ıdaj´ıc´ı multimnoˇziny M . Samozˇrejmˇe vˇsechna slova obdrˇzená z w permutac´ı znak˚ u jsou reprezentována stejnou multimnoˇzinou M . ε pˇredstavuje prázdnou 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ýv´ ame objekty, • e je z´ akladn´ı objekt kolonie, který nazýv´ 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ý 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ý program obsahuje pr´ avˇe c pravidel v jednom z n´ asleduj´ıc´ıch tvar˚ u: a → b, pravidla v daném tvaru nazýv´ ame pˇrepisuj´ıc´ı pravidla, c ↔ d, pravidla v daném tvaru nazýv´ ame komunikaˇcn´ı pravidla, r1 /r2 , pravidla nazýv´ 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án (zmˇenˇen) na objekt b. Druh´ y typ pravidel naz´ yváme komunikaˇcn´ı pravidla a maj´ı tvar c ↔ d. Pokud je dané pravidlo aplikov´ ano, objekt c uvnitˇr agenta a objekt d vnˇe agenta si zamˇen´ı pozice, to znamená, ˇze po vykon´ an´ı pravidla objekt d se nacház´ı uvnitˇr agenta a c je obsaheˇzeno v prostˇred´ı. V práci [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á vyˇsˇs´ı prioritu pro vykon´ an´ı neˇz pravidlo r2 . To znamen´ a, ˇze agent pokud je to moˇzné aplikuje pravidlo r1 , v opaˇcném 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ého agenta pˇrepisuj´ıc´ı programy mo-

Poˇcáteˇcn´ı konfigurace P kolonie je (n + 1)-tice (? o1 , . . . , ? on , ? vE ) multimnoˇzin objekt˚ u nacházej´ıc´ıch se v P kolonii na zaˇcátku v´ ypoˇctu, kde ? oi pro 1 ≤ i ≤ n a pro prostˇred´ı ? vE . Obecnˇe konfigurace P kolonie Π je definovaná jako (? w1 , . . . , ? wn , ? wE ), kde |? wi | = c, 1 ≤ i ≤ n, ? wi a reprezentuje vˇsechny objekty i-tého 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ánku prob´ıhá paralelnˇe. V kaˇzdém kroku paraleln´ıho v´ ypoˇctu pracuje maximáln´ı 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ávˇe jeden a pouˇzije ho. Pro programy z kaˇzdé mnoˇziny Pi zavedeme oznaˇcen´ı z mnoˇziny lab (Pi ) takové, ˇze lab (Pi ) ∩ lab (Pj ) = ∅ pro i 6= j, 1 ≤ i, j ≤ n. Pro formáln´ı vyjádˇ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á, pokud mnoˇzina oznaˇcen´ı program˚ u P splˇ nuj´ıc´ı podm´ınky v´ yˇse, nem˚ uˇze b´ yt vybrána, jinak neˇz jako prázdná 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áln´ıho symbolu f v prostˇred´ı. Mnoˇzina ˇc´ısel poˇc´ıtan´ ych P koloni´ı Π je definována 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áteˇcn´ı konfigurace, (? w1 , . . . , ? wn , ? wE ) je koncová konfigurace, a ⇒∗ oznaˇcuje reflexivn´ı a tranzitivn´ı uzávˇer ⇒. Mˇejme P kolonii Π = (A, e, f, ? vE , B1 , . . . , Bn ). Maximáln´ı poˇcet program˚ u asociovan´ ych s agenty naz´ yváme v´ yˇskou, poˇcet agent˚ u, n, pak stupnˇem a poˇcet objekt˚ u uvnitˇr kaˇzdého agenta kapacitou P kolonie. Oznaˇcme N P COLpar (c, n, h) tˇr´ıdu mnoˇzin ˇc´ısel poˇc´ıtán´ 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é 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á, ˇze

Registrov´ y stroj

p∈P

V naˇsem pˇr´ıspˇevku porovnáváme 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áln´ı, 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án do i 1≤i≤n mnoˇziny P tak, aby splˇ noval podm´ınky dˇr´ıve uvedené

Definition 2 [9] Registrový 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é oznaˇcen´ı urˇcené pomoc´ı mnoˇziny H.

Obecnˇe pro kaˇzdé j, 1 ≤ j ≤ n, pro které 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é j, 1 ≤ j ≤ n, necht’ ? wj0 = ? wj a dále 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ého stroje maj´ı následuj´ı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ásleduj´ı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é koncové oznaˇcen´ı lh . Bez ztráty na obecnosti m˚ uˇzeme pˇredpokládat, ˇze v kaˇzdé ADD-instrukci l1 : (ADD(r), l2 , l3 ) a v kaˇzdé SU B-instrukci l1 : (SU B(r), l2 , l3 ) je oznaˇcen´ı l1 , l2 , l3 navzájem r˚ uzné. Registrov´ y stroj M poˇc´ıt´ a mnoˇzinu N (M ) ˇc´ısel následuj´ıc´ım zp˚ usobem: na zaˇc´ atku jsou vˇsechny registry prázdné (je v nich uloˇzeno ˇc´ıslo nula) s instrukc´ı oznaˇcenou l0 a pˇrejdeme k aplikován´ı instrukc´ı urˇcen´ ych pomoc´ı oznaˇcen´ı (doc´ıl´ıme pomoc´ı obsahu registr˚ u). Pokud dojdeme ke koncové instrukci, pak ˇc´ıslo uloˇzené v daném okamˇziku v registru 1 pˇredstavuje v´ ysledek z´ıskan´ y registrov´ ym strojem M a od této 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á.) T´ımto zp˚ usobem v´ ypoˇctu m˚ uˇzeme vypoˇc´ıta vˇsechny mnoˇziny ˇc´ısel, které jsou vypoˇcitatelné Turingov´ ym strojem. [9]

3

P2 : 1 : he → Di 2 : hD ↔ l0 i

Agent B1 generuje a pos´ılá kopie oznaˇcen´ı pro startovac´ı instrukci l0 registrového stroje M a zastav´ı se pˇr´ıjmut´ım jedné 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áln´ı objekt d.

agenta

generuj´ıc´ıho

P3 : 1 : he → di 2 : hd ↔ H/d ↔ ei V kaˇzdém druhém 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ává 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éto ˇcásti se budeme zab´ yvat vlastnostmi P kolonie pouze s jedn´ım objektem uvnitˇr kaˇzdého 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á z prostˇred´ı objekt l1 a generuje m´ısto nˇej objekt ar , nakonec vymˇen´ı objekt l2 nebo l3 za e. Na závˇer této ˇcásti 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á 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án 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énˇ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átku v´ ypoˇctu agent generuje objekt l0 (oznaˇcen´ı startovac´ı instrukce registrového stroje M ) a dvˇe kopie objekt˚ u a. Agent zaˇc´ıná simulaci instrukce oznaˇcené l0 a generuje oznaˇcen´ı následuj´ı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án´ı instrukce oznaˇcené li (s objektem li um´ıstˇeném v prostˇred´ı). Toho je dosaˇzeno n následuj´ıc´ımi kroky: Agent zaˇc´ıná v´ ypoˇcet generován´ım objektu d. Pro dalˇs´ı kroky v´ ypoˇctu mus´ı generovat ˇctyˇri objekty d. Druhá dvojice objekt˚ u d m˚ uˇze b´ yt pˇrepsána na pomocné 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é 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é li (Pokud objekt li je um´ıstˇen v prostˇred´ı). Inicializace je vykonána pomoc´ı následuj´ıc´ı posloupnost´ı krok˚ u:

Ukázali jsme, ˇze P kolonie Π simuluje v´ ypoˇcet registrového stroje M . V´ ypoˇcet P kolonie Π zaˇc´ıná bez objekt˚ u ar v prostˇred´ı, stejn´ ym zp˚ usobem zaˇc´ıná v´ ypoˇcet registrového 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é instrukce oznaˇcené 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ázkou je, jak´ y poˇcet agent˚ u je nutn´ y pro simulován´ı registrového stroje. V pr´ aci [2] je dokázáno: 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ém programu dvˇe pravidla. Pokud pravidla v programech jsou stejného 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ého 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ázdn´ y). V pˇr´ıpadˇe, ˇze ano, pˇr´ıdá l1 s ar dovnitˇr, v pˇr´ıpadˇe, ˇze ne, l1 vstoup´ı do agenta se symbolem e. V závislosti na obsahu agenta generuje objekt l2 nebo l3 .


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ázdn´ y: konfigurace Π

krok 1. 2. 3. 4.

Pokud agent pouˇzije program 3 ve druhém 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


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án´ım l2 nebo l3 . Tento objekt mus´ı b´ yt poslán ven do prostˇred´ı s objektem v. konfigurace Π

P 25 27 29 ?

V´ ypoˇcet v pˇr´ıpade, kdy registr r nen´ı prázdn´ y:

2. Pro kaˇzdou ADD-instrukci l1 : (ADD(r), l2 , l3 ) pˇridáme do mnoˇziny program˚ u P: P : 14 : 15 : 16 : 17 : 18 : 19 :


P : haa ↔ hlh i


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ázali jsme, ˇze P kolonie Π simuluje ˇcinnost registrového stroje M a ˇc´ıslo z´ıskané v prvn´ım registru registrového stroje M odpov´ıdá 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ále. Obsah registru i bude reprezentován 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ého stroje M a zastav´ı se pˇrijet´ım jedné 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átek 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ázdn´ 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ád´ı dovnitˇr objekt l1 a jednu kopii ar (pokud je nˇejaká 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.


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ásleduj´ıc´ı mnoˇzinou program˚ u:

P2 : 1 : hee → Dei 2 : hDe ↔ el0 i

konfigurace Π

B l1 ? ee ? el1 ? ar l2 ? ee


B l1 ? ee ? ar l1 ? l2 v ? ee

Env ? l1 ar

? l2 v


Pl1 1 2 3 ?

V´ ypoˇcet pro pˇr´ıpad, kdy registr r je prázdn´ 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éto ˇcásti v´ ypoˇctu objekt s oznaˇcen´ım dalˇs´ı instrukce registrového 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


Pl1 1 2 3 ?

4. Pro koncovou instrukci lh nen´ı zde program ani ˇzádn´ y agent P kolonie. 5. Druhá moˇzná posloupnosti krok˚ u na ˇzaˇcátku 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.


Env

? el0 ? el0

P1 1 2 1 2 1 −

P2 1 − − − 2 −

Pl0 − − 1 2

[3] Csuhaj-Varj´ u, E. — Kelemen, J. — Kelemenová, 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ázali jsme, ˇze P kolonie Π simuluje ˇcinnost registrového 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é instrukce oznaˇcené 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 grammartheoretic treatment of multi-agent systems. Cybernetics and Systems 23, 1992, pp. 621–633.

Homogenn´ı P kolonie jsou v´ ypoˇcetnˇe u ´plné pro: 1. c = 1, h = 6 a neomezené n (P kolonie s jedn´ım objektem uvnitˇr kaˇzdého agenta, s pouˇzit´ım nejv´ yˇse ˇsest program˚ u)

[7] Kelemen, J. — Kelemenová, 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é h (P kolonie sestaven´ a ze ˇctyˇr agent˚ u, kaˇzd´ y z n´ıch má uvnitˇr pouze jeden objekt) 3. c = 2, h = 4 a neomezené n (P kolonie se dvˇema objekty uvnitˇr kaˇzdého agenta, s pouˇzit´ım nejv´ yˇse ˇctyˇr program˚ u)

[8] Kelemen, J. — Kelemenová, 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éh (P kolonie s jedn´ım agentem, kter´ y zpracovává dva symboly). Pro dané v´ ysledky byla pouˇzita simulace registrového stroje. V´ yzkum simulace operace ADD urˇcuje obdrˇzené 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á, 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 ńora 2008

[2] Cienciala, L. — Ciencialov´ a, L. — Kelemenová, A.: On the Number of Agents in P colonies,

79

80

Homogenní P kolonie 1

Recommend Documents